Occam and TransputersOccam: An Explicitly Parallel LanguageTransputersOccam BasicsComposing Sequential ProcessesComposing Parallel ProcessesPAR for parallel executionReplicated PARAlternationChannel ProtocolsConfiguration6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 1. © Krste AsanovicKrste [email protected]://www.cag.lcs.mit.edu/6.893-f2000/Occam and Transputers6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 2. © Krste AsanovicOccam: An Explicitly Parallel LanguageOccam based on Communicating Sequential Processes (CSP) formalism developed by Tony Hoare, Oxford, UK, and an experimental language by David May, Bristol, UKDesigned to have a formal semantics suitable for automatic program transformationsMany groups investigated direct translation of Occam into hardware6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 3. © Krste AsanovicTransputersThe transputer architecture was designed as an Occam engineTransputer C compiler didn’t appear until much later, and initially produced inferior code compared with Occam compilerOriginal target for transputer was embedded control (robots) where interfacing to hardware directly was importantDesigned to allow large arrays of transputers to be connected easilyAlmost no glue logic required for minimal transputer node6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 4. © Krste AsanovicOccam BasicsOccam primitive is a process, five kinds:Assignment x := y + 2Input keyboard ? charOutput screen ! CharSkip SKIP -- NOP that terminatesStop STOP –- NOP that never terminates Channels provide communication between processesUnbuffered, point-to-point synchronous communicationChannels have declared protocol typesc ? yc ! xChannel c6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 5. © Krste AsanovicComposing Sequential ProcessesSEQ executes sub-processes sequentiallySEQkeyboard ? char –- read char from keyboardscreen ! char -- write char to screenCan do replicated SEQSEQ i = 0 FOR array.sizestream ! data.array[i]-- equivalent toSEQstream ! data.array[0]stream ! data.array[1]...6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 6. © Krste AsanovicComposing Parallel ProcessesPAR executes sub-processes in parallelPARkeyboard(kbd.to.ed)editor(kbd.to.ed,ed.to.screen)screen(ed.to.screen)screeneditored.to.screenkeyboardkbd.to.ed6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 7. © Krste AsanovicPAR for parallel execution WHILE next <> EOF SEQ x := next PAR in ? next out ! x * xRestrictions on parallel data accessvariables modified in one arm of PAR cannot be read or written in other parts of PAR, e.g., PAR -- this PAR is invalid SEQ mice := 42 -- assigns to mice c ! 42 c ? mice -- assigns to mice6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 8. © Krste AsanovicReplicated PARCan use replicated PAR to build array of parallel processesPAR farmer() PAR i = 0 FOR 4 -- count must be constant worker(i)array of channels used to connect processes (not shown in code snippet)worker(1) worker(2)worker(0) worker(3)farmer()6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 9. © Krste AsanovicAlternationALT combines a number of processes only one of which is executedEach process has a guard:input on channelwait on timercan be predicated with boolean expression ALT left ? packet -- guard input statement stream ! packet right ? packet –- guard input statement stream ! packetPRI ALT prioritizes sub-processes in textual orderALTleftrightstream6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 10. © Krste AsanovicChannel ProtocolsAll channels have set of legal message types, the channel protocol. Compiler checks all uses of channels to ensure all communications are compatible with type of channel.CHAN OF [36]BYTE message : -- explicit array typeCHAN OF COMPLEX32 imp : -- named record (struct)CHAN OF INT::[]BYTE link: -- length + vectormessage ! “Hello, World!”link ! len::[buffer FROM start]Also supports tagged type channels, and sequential message channelsGoal is type-safe communication6.893: Advanced VLSI Computer Architecture, November 7, 2000, Lecture 7, Slide 11. © Krste AsanovicConfigurationOccam application written as network of communicating processesConfiguration step maps parallel process components onto available physical processors and maps channels to hardware linksConfiguration should not change
View Full Document
Unlocking...