I can't remember where I saw the map but I'm sure that the Western Isles, the west coast of Scotland and northern Ireland were once one nation - going back to the seas being the highways again. I'm guessing what you are talking about is where the people who settled on those islands and coastal areas originated from. I'd love to know because they would have been the builders of Brodgar and Callanish.

http://www.biggararchaeology.org.uk/pdf_reports/018-023-HowburnFarm.pdf

Scotland was not effectively prehistoric in the Pictish period (I presume by Pictish period you mean around 300AD until about 843AD). There were plenty of written records from the period 300-843AD. Some still survive. One of the main problems with Scotland's ancient written texts on vellum and parchment and stuff was King Edward and King Henry. They burned down a LOT of our history and most of our written historical documents were destroyed. Texts are rare. Iona has some Pictish Period documents referring to King lists etc but these are written in Latin. Adamnan was writing in Iona in the 7th Century. But like most writings from that period in England, Wales and Ireland they are in Latin.

The Galloway crowd had been into writing since St Ninian kicked off at the Isle of Whithorn in the 4th Century. In the 8th century a Whithorn monk wrote the poem "Miracula Nynie Episcopi". Dun Rheged was just along the road at Dunragit and the area around Whithorn has produced 4th and 5th Century Latin inscribed stones.

Latinus Stone

http://www.whithornpriorymuseum.gov.uk/whithorn/whithornhome/whithornabout/whithornmuseum/whithornlatinusstone.htm

Or this more christiany one.

http://www.dumfriesmuseum.demon.co.uk/whitprymuse.gif

There's rather famous Cat Stone from the 4th Century from the cist cemetery at Kirkliston. It has some lovely writing on it.

http://canmore.rcahms.gov.uk/en/site/50719/details/the+cat+stane/#

http://canmore.rcahms.gov.uk/images/l/488207/

There is also the marvellous collection of Latin inscribed Stones from the Antonine Wall and from various forts and installations from Galloway to Angus in the North East.

Distance Slabs like these.
http://www.antoninewall.org/images/roman_images/F.1969.22.jpg

http://www.athenapub.com/scobrn3.GIF

Altars like this

http://www.antoninewall.org/images/roman_images/altar.jpg

Gravestones like this

http://www.antoninewall.org/images/roman_images/tombstone.jpg

and this

http://www.scotland.gov.uk/Resource/Img/253350/0072602.jpg

Not far from me in the Manor Valley lay the (6th Century) Coninie Stone (now in the Peebles Museyroom).

http://www.biggararchaeology.org.uk/images/CONINE_ST_01_260.jpg

The Yarrow Stone has some lovely latin writing. It commemorated a BIG battle in the 5th/ 6th century.

http://flic.kr/p/8fqbct

Scotland was full of literate communities during the Pictish Period.

Examples like "The Goddodin" are exceptionally rare and although originally (in all probability) written in Edinburgh and only surviving in a 13th Century copy, part of it refers to the Battel of Strathcarron between the Strathclyde Britons and the Scots of Dalriada. Yet some of the warriors referred to in other parts of the poem are Picts.

I'm often down at Gatehouse of Fleet in Galloway. They recently had another dig at Trusty's Hill the site of the Southernmost Pictish Carvings ever found (and lovely they are too). You might find this website helpful and informative.

http://gallowaypicts.com/wordpress/discovering-dark-age-galloway/