Automated compilation of concurrent programs into self-timed circuits Citation Burns, Steven Morgan (1987) Automated compilation of concurrent programs into self-timed circuits. Master's thesis, California Institute of Technology. doi:10.7907/j438-dz84. https://resolver.caltech.edu/CaltechTHESIS:03272012-085559361 Abstract No abstract. Item Type: Thesis (Master's thesis) Subject Keywords: Computer science Degree Grantor: California Institute of Technology Division: Engineering and Applied Science Major Option: Computer Science Thesis Availability: Public (worldwide access) Research Advisor(s): Unknown, Unknown Thesis Committee: Unknown, Unknown Defense Date: 1 December 1987 Other Numbering System: Other Numbering System Name Other Numbering System ID Computer Science Technical Report 88-02 Record Number: CaltechTHESIS:03272012-085559361 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:03272012-085559361 DOI: 10.7907/j438-dz84 Related URLs: URL URL Type Description http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-02 Related Item Computer Science Technical Report 88-11 in CaltechAUTHORS Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 6872 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 27 Mar 2012 16:24 Last Modified: 09 Nov 2022 19:20 Thesis Files Preview PDF - Final Version See Usage Policy. 2MB Repository Staff Only: item control page

Automated Compilation of Concurrent Programs into Self-timed. Circuits Steven M. Burns Computer Science Department California Institute of Technology Caltech-CS-TR- 88-2. Automated Compilation of Concurrent Programs into Self-timed Circuits Thesis by Steven M. Burns In Partial Fulfillment of the Requirements for the Degree of Master of Science Caltech-CS-TR-88-2 California Institute of Technology Pasadena, California December 1987 Contents 1 The Programming Language 1.1 Sequential Constructs 2... ee ee ee ee 1.2 Procedures .......-. 2... eee ee ee ee 1.3 Concurrency 2.2... . . ee et ee es 1.4 Definition and Instantiation .......... ee ee ee we eee ns 1.5 Grammar Rules... . 1. ee ee ns 16 New Constructs... 0.0.0... 2 fe ee ee ee ees 2 Decomposition 2.1 Abbreviations... 2... ee ee eee 2.2 Decomposition and Sub-Processes. 2... 2. ee ee 2.38 Syntactic Decomposition... 2.2... ee ee ee ee 2.4 Non-Syntactic Decompositions ............ - eee ee ee es 2.4.1 Sequencing Sub-process ......... 0.00. tet e eee eee 24.2 Control Sub-Process .. 1... 0... eee ee eee ns 2.4.3 Exclusive Guards... 2... ee ee ee ees 2.4.4 Non-exclusive Guards .. 1... . ce eee ee te tt ee ee 2.5 Example... .. 0.0... ee ee ee ee et ee eee 3 Compilations 3.1 Symopsis . . 1... ee ee eee 3.1.1 Handshaking Expansions ............000 00000 ueae 3.1.2 Production Rule Sets .. 2.2... 0... 0... eee ee ee 3.1.3 Operator Sets... 0. ee es 3.1.4 Extensions for Non-stable and Non-exclusive Program Constructs 3.1.5 Application to Our Problem. ................22200. 3.2 Communication Channels .. 1... 2... ce eee eee ees 3.8 Probe and Variable Values... 2... 1. ee es 3.4 Compilations of Syntactic Forms 2... 1... ee ee 3.4.1 Parallel Composition... 2.2.2.2... -. 0.0... eee eee ee ee 3.4.2 Skip Statement .......0.0.0.0 0000 002 2 ee eee ee eee 3.4.8 Assignment Statement... ...... 0.000 0c eee eee ees oon f 24 ii 4 3.4.4 Sequencing Sub-process ....... 2... eee ee reece eee nes 28 3.4.5 Control Sub-process ... 2... 0.2... eee ee ee ee ee 29 3.4.6 Communication Actions .......... 000. ee eee eee eee 31 3.4.7 exclusive Guards... 1. ee te ee es 37 3.4.8 Non-exclusive Guards ............-.20 005% bee ee 37 3.5 Example... .... 0... eee eee ee eee ee ee ee ene 38 Isochronic Forks 41 4.1 Electrical Solution 2... . 0... eee ee ee eee eee 41 4.2 Algorithmic Solution... 1... ee we ee ee ee es 41 4.2.1 Variable Distribution and Completion Detection ........... 42 4.2.2 Process Suspension. .......... 0 ec eee ee tee te ene 42 Circuit Optimization 47 5.1 Removing D-elements .......... 2.000 ee ee nee eee 47 5.2 Sequencing Operators . 2... 2... ee ee te tt te es 48 5.38 Passive Channels... 2... 1... ee eee ee ee Lek eee eee 48 5.4 Special Circuits for Arbitration ..............2004 alee eee 50 0.09 Example... . 2. ee ee ee ee eh ee es 51 List of Figures 11 1.2 1.3 1.4 1.5 1.6 1.7 21 2.2 2.3 2.4 2.5 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 Sequential Constructs 2.0... . eee ee ee ee ee ee ee ee 3 Procedure Syntax... 0... ee ee ee ee ees 4 Concurrency Constructs 2... 0. et te ee es 5 Hoare Triple Semantics of the General Communication Action. ....... 6 Definition and Instantiation Constructs ..........0..2.0-0000% 7 Program for Mutual Exclusion Ring ................0.0000. 8 BNF Description of the Programming Language ............... 10 Expanded Process privO 2... 1 ee ee ee ee 13 Register and Procedure Decomposition of priv? .......0...0.0020- 15 Resulting Process Forms After Syntactic Decomposition ........... 16 Syntactic Decomposition of the priv0 process ...........000008 17 Decomposition of the guards in the priv? process ............20.. 21 Production Rule Sets for Operators... 1... ee ee es 24 Primitive Process Definitions ... 2... 0... cece eee ee eee ee 25 Compilation of Assignment Statement ......0.0...0. 000 ce ee nee 28 Compilation of Sequencing Process ..........2...0000.-00004 29 Production Rule Set for the Control Process. .........-0.--00 005 30 Circuit for Control Sub-process (K=2,n=4)....... 0.00 eee aes 31 Circuit for Active Communication (n=3,j=0) ..........2.00.5 32 Production Rule Set for the Passive Communication ............. 33 Circuit for Passive Communication (n=3,f=0) ............... 34 Passive k — (m,n) Expansion Circuit (k =2,m=2,n=38) o........ 36 Active k — (m,n) Merger Circuit (k =2,m=8,n=2)............ 36 Exclusive Conjunction»... 00. et ee ee ee es 39 Simple Variable. 2... ee ee ee ees 39 Simple Probe... 6... ee ee eee ee ee 39 Conjunction... 2... ee ee eee 39 Disjunction 2... ee ee eee 39 Busy Evaluation ............ ee ee 39 Complete Circuit for priv? Process 2... 1 ee ee ee 40 ii iv 4.1 4.2 4.3 4.4 AS 4.6 5.1 5.2 5.8 5.4 5.5 Distribution and Detection Using a Lusear Ordering ...........4.% 42 Concurrent Distribution and Detection... 2.2... 2. eee ee 43. Modified 2 — (3,2) Active Merger... 0... 0... pe eee ee ees 44 Modified Passive Communication ......0.......2.02.00 0000s 45 Modified 2 — (2,3) Passive Expansion .. 1.0.0... 0000 ce eee 46 Modified Assignment... ... 0.0... ce eee ee ee ee eee 46 Another Sequencing Circuit... 2... ee et ee ee es 48 Comparison of Passive Communication Implementations. .......... 49 Reshuffled Circuit for Multiple Passive Communications ........... 51 Non-busy-waiting Arbiter... 0.0... eee ee ee ee eee 51 Optimized Circuit for the priv? Process ........0...00200 05 eee 52 Introduction While the size of circuits implemented on single VLSI chips has increased year to year, tools and abstractions for managing the complexity of these systems have not been developed at an equal pace. We propose a framework for developing provably correct digital systems from an abstract specification through a series of semantics preserving transformations. Specification = Concurrent Program -» Operator Set = VLSI Chip The system designer translates the system specification into a concurrent program in a high-level language with a simple semantics. It is in this form, and not the final form of the digital circuit, that the designer proves the system is an implementation of the specification. In this first transformation step, the designer may apply the tools of concurrent program development and verification. The concurrent program is then transformed into a semantically equivalent self-timed circuit. Alain Martin[5,7| describes a general framework for performing these transforma- tion. In this thesis, we describe a way of automating the compilation procedure. The final task is the realization of the operator sets in a computing medium such as a VLSI chip. One approach is to implement each operator as a CMOS standard cell and use placement and routing techniques to position and interconnect the cells. In this thesis, we are only concerned with automatically transforming concurrent pro- grams into self-timed operator sets. The body of this thesis is divided into five logical sections: e We define a concurrent programming language, a variant of CSP that includes syntax for interconnecting any number of sequential processes. e We show how to systematically break up large processes into more manageable units based on the basic constructs of the language. e We implement each basic construct as a collection of self-timed operators. e We provide refinements to implement processes of arbitrary size by fixed-size con- structs. e We discuss optimization strategies to improve these circuits, Chapter 1 The Programming Language We chose to develop a new language for specifying concurrent programs. Our language is based on CSP[3] with the probe[8]. A few new constructs have been added to facilitate efficient implementation in VLSI. The new constructs reduce the number of explicit variables needed in some programs by introducing more control structures. The language is described in a bottom-up manner by incrementally extending BNF descriptions of the syntax as the new constructs are introduced. A complete description of the language syntax is given later in the chapter. The low level entities used as terminals in the BNF descriptions are tokens corresponding to punctuation symbols, names and integers. All punctuation symbols appear in the BNF as strings surrounded by single quotes. The tokens NAME and INT denote terminal symbols for names and integers. 1.1 Sequential Constructs The sequential parts of our language differ from CSP in only a few ways. We allow only boolean valued variables. Assignments to true or false are denoted by the raising (xt) or lowering (x |) of a variable. The selection statement has been extended to allow repetition in a subset of cases. Syntactically, a ‘*’ is appended to the end of the guarded command if after the guarded command is executed, the selection statement is to be repeated. For example, the guarded structure a; [G1 — Si;%|G2 — Sy]; 8 has the following operational semantics: After the completion of the arbitrary program part a, both Gy and G2 are evaluated. If G, is true, the command Sj is executed and the flow of control is returned to the beginning of the guarded structure. If Go is trne, the command Sg is executed but the flow of control continues with 6. Ifboth G, and G- are false, the program waits until G; V Gz becomes true. In the case where both G, and G2 are true, we may define the semantics in two ways. The programmer may choose the interpretation which is most efficient or convenient for a particular program by using different syntactic symbols (seq process) ::= {(decl}} (sequence) (decl} ::= (variable decl) (variable decl) ::= boolean (boolean spec) {‘,’(boolean spec)} {boolean spec) ::= NAME |‘=’ (true | false) | (sequence) ::= (statement) {‘;’(statement) } (statement) ::= skip | (assignment) | (guarded structure) (assignment) ::= NAME (‘T? | ‘|| ‘:=’(expr)) (guarded structure) ::= (‘[’ | ‘*[’) (guarded command set)‘]’ | ‘+[?(sequence) ‘| ‘[{expr) {guarded command set) ::= (guarded command) { (‘|’| ‘]’) (guarded command) } (guarded command) ::= (expr)‘—’ (sequence) [‘;*’| (expr) u= (conjunct) {*v’{couj unc) } (conjunct) ::= (literal) {‘A’(literal)} (literal) ::= [‘-’] (primary) (primary) ::= true | false | NAME | ‘(’(expr)‘)’ Figure 1.1: Sequential Constructs as separators between the guarded commands. By using the ‘|’ (read thickbar) separator, the programmer specifies that an arbitrary but mutually exclusive choice is made between the commands S; and S3. If the programmer chooses the ‘|’ (read thinbar) separator, he specifies that no choice will ever need to be made, that is, at most one guard will be true each time the selection statement is executed. The semantics of a selection statement with the of a selection statement with the ‘]’ separator. ‘? separator may be defined in terms [Go —_ ao| oe AGn-1 —_ On—1] is semantically equivalent to [Go — ag] ...[|Gn-1 — an-i| V G; \G; —> abort | tAd If more than one guard is true when the guards are evaluated, the abort statement may be reached, and thus no post-condition of the selection statement may be guaranteed. We introduce the following abbreviations: e [|G —+ skip | may be written more concisely as [G]. We call this construct a wait. e Infinite repetition, [true —> S;+%| may be rewritten as +[S]. e The iteration construct, #(Go —> aol]... |Gn—-1 — an-1] is an abbreviation for ; n-1 [Go —* ag;*]...[Gn-1 — on_15*]5 V G; — skip] #=0 All occurences of ‘|’ may be replaced by the ‘|’. e The assignment statement v := FE is an abbreviation for [E — vf |nB— vl] 1.2 Procedures (decl) ::= (procedure decl) {procedure decl).::= procedure NAME(sequence) (statement) ::= (procedure call} (procedure call) := NAME Figure 1.2: Procedure Syntax Procedures provide a means of sharing code in a sequential process. Procedure declarations of a process are mixed together with port and variable declarations. Statements in the procedure body may reference the ports and variables of the parent process. We specify procedure calls by referencing the procedure’s name. Recursion is not allowed. 1.83 Concurrency A collection of processes will operate concurrently if defined together in a parallel compo- sition statement. A process is either a single sequential process or a (nested) collection of sequential processes. Synchronization between two processes is accomplished by zero-slack communication actions across communication channels denoted by pairs of named ports. For any given channel, one process may determine whether the other process is waiting on this commu- nication by evaluating a boolean condition called a probe. These prohes may be used in arbitrary boolean expressions. Only one of the two processes connected by a channel may use the probe. The port which initiates the communication is called active. The other port, which may use the prohe, is-called passive. The decision of which port is active and which port is passive must be made at compile time. In our language, the programmer explicitly declares a channel as an active-passive pair of ports. Concurrently operating processes may not share variables. However, processes may share data by sending values from a small finite set during a synchronization. As an example, (process) ::= (seq process) | ‘(’(process) {‘||’(process) } ‘)’ {(channel decl)} (statement) ::= (communication) (communication) := NAME [‘(INT‘)} [f:"[(response) {‘|’{response) } {]’] | NAME‘?’NAME | NAME‘Y’ (expr) (response) ::= INT‘—>’(sequence) (primary) c= NAME ['CINT’) {channel decl) ::= channel (channel spec) {‘,’(channel spec) } {channel spec) ::= ‘’NAME‘,NAME‘)’ (decl) ::= (port decl) (port decl) ::= (passive | active) (port spec) {‘,’(port spec) } (port spec) := NAME [‘VINT‘ INT‘) | ‘2? | V7] Figure 1.3: Concurrency Constructs consider a pair of processes with an interconnecting channel. One process cyclicly sends the values 0, 1,2 across the channel (LZ, R) to a second process. The second process cyclicly performs a read communication and based on the value received executes the code segments a, 8 or y. We may code such a process pair by (active L(3, 1) +[L(0); Z(1); L(2)| \|passive R(1, 3) 4[R : [0 — all — f)2 — 9] )channel (L, R) We note now that the language construct R: [..] is not a selection statement. It denotes a communication action from the port R. Alternate executions occur based on the value received by the communication. In this example, the port L sends a value to port R. We specify the set of values that may be sent from L by a single integer, in this case 3, short for the set of values {0, 1,2}. We use 1 to represent the set of values {0} that may be sent from R to L. Note that the value set {0} consists of a single value and thus no data is transferred from R to L during the synchronization. When a port is declared, both its send and receive sets are specified. Its name and its active or passive nature are also included in the declaration. There need be no association between the direction of information flaw and the active or passive nature of the port. The port declarations passive (3,1) and active R(1, 3) are also perfectly valid. As a natnral generalization of the commnnication constrict, data may he sent in both directions during a synchronization. When declaring a channel, one may specify both multiple input values as well as multiple output values. Also, the probe is generalized to test which value the other process is sending before actually performing the communication action. All communications will be defined in terms of this general form. {cL=CA0<t<m}L(t): [0 — {eL=C+1Aj=D0}ao Jl—- {ceL=C+1Aj=laq In -—1— {eL=C+1Ajg=n-1}on-1 | {cR=CA0<j<n}R(j): [OS {eR=C+1IA1 =0}H |i — {cR=C+1IAI=]} A Im—1— {cR=C+1At=m-1}Bn-1 Figure 1.4: Hoare Triple Semantics of the General Communication Action We give a more formal semantics of the general communication action by introducing the ghost variables cX and qX attached to the communication port X. The integer valued variable cX represents the number of completed communication action through the port X. The boolean qX states whether X is ready but not able to finish a communication action. The standard zero slack axioms apply[4]. aqLv 7Aqk cL=cR A Hoare triple semantics of the data transmission mechanism is given in Figure 1.4. The communications L and FR are performed by separate sequential processes. Information is exchanged during the communication. One of m values is transmitted from port LE to port R, Simultaneously, one of n values is sent from R to L. The synchronization axioms require the communication action to complete simultaneously. After the exchange has completed, the control flow of each process continues with different sequences of commands based on the values received during the communication. The passive-active distinction is only needed when the probe is used. Let L be a passive port. Then, we define the meaning of the probes L(0),..., L(n —1) of Las L(k) > (aR Ak = 5) (QR Ak = j) > OL(k) The diamond is a formalism borrowed from temporal logic, meaning eventually the predicate following the diamond will hold. In this case, if R is suspended and k = j, the probe L(k) will eventually hold. Various abbreviations apply to the communication syntax. Consider the LE action in Figure 1.4. e L(t) means L(t) : [0 —>+ skip] and is only applicable if L has only one input value. ° If Z has only one output value, the abbreviation L: [a1 — fy|...lan — Br] means E(0) : [a1 — fy|.-.|an —> Bn] £ combines the two previous abbreviations. LZ means (Z(0)V...V E(n — 1)). In port declarations, L? and L! are short for L(1,2) and L(2, 1), respectively. Liz abbreviates L : (0 —> x] |1 — 2] LIE abbreviates [EZ —>+ L(1)|n£ — L(0)| 1.4 Definition and Instantiation (program) ::= {(process def)} (program def} (program def) ::= (process) program NAME [(port list)] (process def) ::= (process) process NAME (port list) (process) ::= {process inst) (process inst) ::= instance NAME (port list) (port list) ::= ‘NAME {‘,NAME}‘)’ Figure 1.5: Definition and Instantiation Constructs A completely specified concurrent program consists of a set of processes and a list of ports to connect with the environment. The (program) nonterminal provides the necessary syntax. The ports connected to the environment are parameters to the program definition. As an aid to the programmer for constructing large sets of processes, we allow processes to be separately defined and assigned a name. These definitions are placed before the program specification. All ports and variables not internal to the definition must be declared as parameters. No variables or ports may be inherited from the surrounding scope when these code segments are instantiated. We illustrate the instantiation mechanism with a complete example (see Figure 1.6), a ring of four processes which insures mutually exclusive access to a single resource[7|. The process ring is created by instantiating three priv processes and one privi process. The L and R ports are connected via channels to form a ring of four elements. The four porte U0, 01, 02,U3 connect to the environment. passive U, L active K boolean b = false procedure P_ [b — skip |b —>+ R] ¥[[(7F —> P;bT;U JZ — P;b|;L I] process privO(U, L, R) passive U, L active R boolean b = true procedure P_ [b —> skip |b —> R] «[(7 — P;bt;U [LZ — P;b|;L l] process priv1(U, L, R) passive U0,U1, U2, U3, LO, £1, £2, L3 active RO, R1, R2, R3 {instance privi(U0, L0, RO) instance priv0(U1, L1, R1) ||instance priv0(U2, L2, R2) |instance priv0(U3, L3, R83) )channel (0, R3),(L1, RO), (L2, R1),(L3, R2) program ring(U0,U1,U2, U3) Figure 1.6: Program for Mutual Exclusion Ring 1. Grammar Rules Figure 1.7 displays a complete BNF description of the context-free syntax of our language. A few context-sensitive rules need to be added. e All names must be declared before they are used. e Hach channel declaration must name one active and one passive port. The number of input symbols of each port must match the number of output symbols of the other. « Only variable names may be used on the left hand side of an assignment statement. e Port names must be used in communication actions. Furthermore, the integer symbols must fall within the range declared. e When instantiating processes or statements, the number and types of parameters must match the number and types in the definition. e Recursive procedure calls are not allowed. «# Only passive ports may be named in probes. e The separators ‘|’ and ‘|’ may not be used in the same selection or repetition statement. e The repetition abbreviation may not be used if any of the guarded sequences use the trailing ‘*’ construct. 16 New Constructs Our language extends CSP in a number of ways. Most of the new constructs were added to reduce the number of explicit variables need to code common programs. Repetitive selection — The following simple repetition is more difficult to code without the trailing ‘*’ construct: oo [X — a; Xj (VY — YY]... Without this control construct, an explicit variable must be added, as in: +0304; %[b — [X — a, X/¥ — Y;8] I... Such iteration constructs are common in concurrent programs using the probe. Branching Communication — The selection-like statement as a part of the communica- tion action was introduced to provide a means of changing the flow of control after a read without the explicit use of a variable. For example, the code segment: 5X: [0 — aoll — ag];..- 10 (program) ::= {(process def)} (program def} {program def) ::— (process) program NAME [(port list)| (process def) ::= (process) process NAME(port list) {port list) ::= ‘NAME {‘,,NAME}‘)’ (process) ::= (process inst) | (seq process) | ‘(?(pracess) {‘||’(process)} ‘)’ {(channel decl)} (process inst) ::= instance NAME‘(’NAME {‘,,NAME}‘)’ {seq process) i= {(decl}} (sequence) (channel decl) ::= channel (channel spec) {‘,’(channel spec) } (channel spec) ::= ‘(’(NAME)‘,’(NAME)‘)’ (decl) = ({port decl) | (procedure decl) | (variable decl)) {port decl) ::= ( passive | active) (port spec) {‘,’(port spec)} {port spec) := NAME [ (‘?INT‘/ INT‘) | ‘?? | ‘V)] (procedure decl) := procedure NA ME(sequence) {variable decl) ::= boolean (boolean spec) {‘,’(boolean spec) } (boolean spec) ::= NAME |‘=’ (false | true )] {sequence} ::= (statement) {‘;’(statement) } (statement) ::= skip | (assignment) | (guarded structure) | {communication) | (procedure call) (assignment) ::= NAME (‘T’ | ‘|’ | ‘:=(expr)) (procedure call) := NAME (guarded structure) ::= us | ‘*[’) (guarded command set)‘]’ | ‘s[(sequence)' | ‘P(expr) ? (guarded command set) ::= (guarded command) { (‘|’ | ‘[’) (guarded command)} (guarded command) ::= (expr)‘—+’(sequence) [‘;’#’ (expr) ::= (conjunct) {‘v’(conjunct) } (conjunct) ::= (literal) {‘A’ (literal) } (literal) := = ae (primary) ( ( ( communication) « = NAME [‘VINT‘)’| [*:“?{response) {‘|’{response) } ‘]’| response) ::= INT‘—>’{sequence) Figure 1.7; BNF Description of the Programming Language 11 requires an explicit variable without this construct. We must use the explicit variable a: 26 X23 [a — agla — ay]... Different Selection Semantics — The distinction between the two different types of selection semantics is necessary on efficiency grounds. Extra circuitry is required to imple- ment the mutually exclusive choice of the ‘]? construct. Tt is needed in some programs, but when the programmer can prove exclusion of the guards, the arbitration circuitry may be avoided.. We have considered allowing the compiler to decide when this optimization can be applied, but then the dynamic nature of the computation can not be considered. There would always be some programs for which mutual exclusion is not detected. We force the programmer to make this optimization decision. Definitions — The definition facility is a compromice between nothing at all and a full- fledged language for constructing process connection graphs. Circuits for each definitions may be separately compiled and connected with the circuit for the main program at the operator level, allowing a concise operator description of programs which generate circuits with regular structures. Chapter 2 Decomposition Our goal is to produce a translation procedure that transforms an arbitrary program of the language introduced in the last chapter into a self-timed circuit. The method we demon- strate faithfully applies the low level techniques described in [7,5]. However, we choose to do most of the work at a higher level by first decomposing each process into a collection of smaller, more easily compiled processes. We use the syntax of the original program ta guide the decomposition. To ease discussion of the translation procedure, we somewhat arbitrarily divide it into several stages. In the actual compiler, more than onc stage might be performed in the same pass through the source code. Stage 1. Each process definition is compiled separately. All syntactic abbreviations are expanded to their most general forms. The resulting expanded form is a syntactically correct process definition. Stage 2. New sub-processes are created to implement assignments to variables and procedures. All assignments to a particular variable in the original process are transformed into communications with a new sub-process designed explicitly to assign values to the variable. Procedure calls are transformed into communications with the new sub-process implementing the procedure body. , Stage 8. We decompose each sequential process into a collection of simple sub-processes, ~ each sub-process implementing a basic construct of the language. Each simple sub-process is associated with a nonterminal (statement) of the source language. Stage 4. Further non-syntax-directed decompositions are performed. One decomposition transforms the nonterminal (sequence) into a collection of simple sequencing sub-processes. Exclusive guard sets are transformed into simple sub-processes corresponding to conjunc- tions of possibly negated variables and probes. Sub-processes that continually poll the values of variables and probes are used as implementations of non-exclusive guard sets. The resulting collection of processes and sub-processes semantically equivalent to the original program may now be implemented as a self-timed circuit. In the next chapter, we develop methods of implementing channels, as well as rules for compiling each of the remaining sub-processes into a self-timed circuit. 12 13 passive U(1, 1), L(1,1) active R(1, 1) boolean } = falsc procedure P [6 —> skip |-=b —> R(0) : [0 — skip ]] [true —> [U(0) —> P;bt;U(0) : [0 — skip] [Z(0) —> P;6|; L(0) : [0 — skip] 3*] process priv0(U, L, R) Figure 2.1; Expanded Process priv0 2.1 Abbreviations All abbreviations are replaced by their implementation in the general form of the construct. In particular, waits, infinite repetitions, iterations and assignments are replaced hy the general forms involving only the selection construct with the optional tailing ‘#’. (see Page 3) Abbreviated communication actions are replaced by full communication actions by filling in both the output value sent and alternate execution paths based on the input received. All the abbreviations described on Page 6 are performed. The expansion of these abbreviations seemingly introduces inefficiencies because the most general construct is potentially more difficult to implement than the simplier constructs. In Chapter 5, we will define optirnization procedures that remove the inefficiencies introduced here. The early expansion of abbreviations eases the discussion of the decompositions without compromising the quality, i.e. the performance in both space and time, of the implementation. The code of the ring program (Figure 1.6) expands to the code shown in Figure 2.1 after these transformations are performed. Notice that the abbreviations for infinite repetition, communication, and probes have been expanded to their general forms. 2.2 Decomposition and Sub-Processes When implementing a complex process, one may wish to divide the process code into pieces and compile the pieces separately. Process decomposition|[5] provides a method of structur- ing the division of process code. A process may be decomposed by moving a statement or sequence of statements from the original process to a new concurrently executing process. Synchronization between the main process and the newly created sub-process is performed by a communication action over a new channel connecting the process and sub-process. For instance, the program part a; B37 14 may be decomposed into a sub-process implementing #, an interconnecting channel, and the original program part with @ replaced by an active communication. (passive D »[[D —> A; D]]|lactive D' a; D!;-y)channel (D’, D) By the structure of this decomposition, no command in the sub-process will execute concur- rently with a command in the original process. This fundamental safety property is always obeyed by the decompositions that follow. We allow the process and sub-process created by process decomposition to share variables and channel ports. The language syntax is extended for the description of the decomposition to allow variables and ports to be shared between processes. This is done by adding the BNF rule: (process) ::= {(decl)} (process) The channel introduced by process decomposition may be implemented more simply than the general communication actions because the signaling protocol of this channel may be interleaved (reshuffled) with other communications. We leave the syntax describing communications on these channels in the abbreviated form as a way of distinguishing them from the general communications specified in the original program. We apply process decomposition to the assignment of variables. All assignments to a particular boolean variable are performed by a single sub-process owning the variable. For example, the sequence of statements efja;01;A;xT is decomposed by introducing a simple register sub-process and two channels. Each assign- ment to a variable is replaced by an active communication to this server process. (passive C, D «|[C — xt;C[D — «|; DI \|active C’, D! C"; a; DI; BC! )channel (C’,C), (D', D) Procedures are implemented by directly applying the process decomposition. The proce- dure body is made into a sub-process and is surrounded by a probed passive communication action. Each procedure call becomes a simple active communication. We apply these decompositions to the process priv@ of our ring example in Figure 2.2. A sub-process for the variable 6 and a sub-process for the procedure P are created during this decomposition. 2.3 Syntactic Decomposition The crux of our implementation strategy is a decomposition of each concurrent program based on its parse tree. As the parser recognizes larger constructs, these larger constructs 15 passive U(1,1), L(1, 1) active R(1, 1) boolean } = false (passive P «[[P — [b — skip |-b —> R(0) : [0 —> skip ]]; P]] ||passive D, 7 +[[D — 61; DIE — 6]; EI] ||active P’, D', E' [true —» [U(0) — P'; D';U(0) : [0 — skip] | Z(0) — P'; E'; L(0) : [0 —> skip] j * )channel Py ce D), (£', E) process priv0(U, L, R) Figure 2.2: Register and Procedure Decomposition of priv0 are divided up, using process decomposition, into sub-processes which implement only a single construct. The splitting is repeated on all the generated sub-processes until the only remaining sub-process forms are those corresponding to a basic statements of the language, as shown in Figure 2.3. Expressions are not sub-divided until the next phase of the decomposition. In this figure, the port names C} and C; represent active and passive ends of synchronization channels. The 4; represent arbitrary boolean expressions and z represents an arbitrary variable. Continuing on with our example, syntactic decomposition of the process priv0 yields the collection of sub-processes shown in Figure 2.4. The first sub-process requires no further decomposition. The next sub-process (#[[P —> ...]]) is decomposed into sub-processes for the following statements: the guarded structure with b and —d in the guards and the communication on R. For brevity, we do not show the expansion of the skip statements into separate sub-processes. The main body of the process is called by a single active communication action G’. Further decomposition yields a sub-process for infinite repetition (guarded by G), one for selection between two boolean expressions (Ff), two for sequencing three active communications (Kg and Ky) and two for performing passive communications (Jo and Jj). 2.4 Non-Syntactic Decompositions 2.4.1 Sequencing Sub-process For simplicity and compatibility with other compilations, we decompose the sub-process «([D — 85 91;...5Sn-13 DI] 16 (process) — (Co||Ci||-- -IIC-1) (sequence) ¥[[C —+ Ch;C};...;C1_3C]] (statement) +[[C —+ skip ;C]] (statement) *[[C, —+ x1;C1|Co — 21|;Col] (statement) +#[[C —>+ [yo —> Co;*|...lyz-1 —*> Ch_i* (statement) ¥{[C —> [yo —> Ch; #]...[yx-1 — CLs (statement) +*[[C —+ A(s) : [0 — Ch]...]n-—1— C_,];C]] Figure 2.3: Resulting Process Forms After Syntactic Decomposition into a number of simple sub-processes of the form *[[C — 8';T';C]] These simple sub-processes may be connected together in a variety of ways as we shall see in Chapter 5. For now, we assume a simple linear chain defined inductively by: (passive C «[[C — St;..5Sh_nC]] |jactiveC’ *[[D — $9;C'; Dl] )channel (C',C) 2.4.2 Control Sub-Process The repetition and selection sub-process is also decomposed before compilation. The sub- process, : #[[D — [yo — $95*].-- ve — Spl .- 4; D]] which is equivalent to *[[D — [10 — Sol.--Ive — 53 DI -- I] is split into two sub-processes with a wide interconnecting communication channel. (active P'(1,n) #[[D — P': [0 — Sf]...|k — SL; D|.. J] |[passive P(n, 1) . *[[P Avo — P(0)].-.[PAam-1 — P(n - 1)]] )channel (P’, P) 17 passive U(1, 1), L(1, 1) active R(1, 1) boolean 6 = false (passive P (passive T +([7 —+ R(0) : [0 — skip];7]] |lactive T" WP > [b> skip Hs —> 79; Py] )channel (T',T) ||passive D, E +[[D — 61; DIE — 6b]; a] ||active P!, D', E' (passive H (passive Ko (passive Jo *[[Jo — U(0) : [0 — skip]; Jo] ||active J§ +[[Ko — P'; D'; J}; Kol] )channel (J§, Jo) ||passive A, (passive J, *[[J1 —> L(0) : [0 — skip}; J1]] ||active J} +[[K1 — Pi; B'; Ji; Kal] )channel (Jj, J1) |lactive KG, Ki +([H —> [O (0) —» KsIT(0) — KY); HI )channel (Kj, Ko), (K4, K1) ||active H' (passive G «[[G — [true — H';4|;G]] ||active G! G! )channel (G',G) )channel (H', H) )channel (P', P), (D', D), (E', E) process priv0(U, L, R) Figure 2.4: Syntactic Decomposition of the priv0 process 18 This decomposition allows the guard sub-process to completely evaluate the guards before the computation continues, providing a nice separation of concerns between evaluation and program flow. None of the actions S} may effect guard evaluation because their activities are sequenced. Ilowever, in some cases this separation introduces au unneeded state in the program flow. In Chapter 5, we discuss way of removing the inefficiencies introduced in this step. This same decomposition is performed on the sub-processes with ‘|’ separators. We now further decompose the guard set sub-processes. There are two types of decompositions, one for each type of separator. 2.4.38 Exclusive Guards In the mutually exclusive guard set - *[[Q A 40 — Q(0)|..-1Q A tn-1 — O(n - 1)]] we know no two guards @ A 4; are true at the same time. We may split this sub-process into n sub-processes of the very simple structure +1 Ans — QO] Each sub-process is then further decomposed independently. This technique is not a legal decomposition if the guards are not mutually exclusive. In the case of non-exclusive guards, this decomposition yields several sub-processes that may run concurrently, violating the fundamental safety requirement. Let F be the boolean expression represented by the syntax Q A+;. If we expand F into sum of products form, F = Vo f;, we may expand the sub-process to have more guards, but each of a simple conjunctive form. We may now use the sub-process #([fo — @()].--[fm-1 — QW] as an implementation of the above sub-process. However, if we want to repeat the decom- position into sub-processes with a single guard, we must insurc mutual exclusion among the f;. We give a simple algorithm for transforming a boolean expression F into a form suitable for implementation by this method. Algorithm: Disjoint Disjunctive Form Let F = Vyec fi; where each f; € C is a conjunction of literals. while 4(f;, fj :C : f; A f; is satistiable) remove f; fromC add each term of the disjunctive expansion of f; A ~f; toC | If we use the sum of products form produced from this algorithm, all mutually exclusive guard sets may be decomposed into collections of sub-processes of this form: #[[Q Ato A...A th-1A 72% A..-A72n-1 — Q(i)]] 19 2.4.4 Non-exclusive Guards The decomposition technique described for exclusive guards suffers from several inadequa- cies. The resulting guards, while being simple conjuncts, are still of arbitrary size. Further- more, the total size of the sub-processes implementing the guard set may be exponential in the number of variables named in the guard set. We may avoid these problems by evaluating the guards sequentially. We consider, for the time being, guard set sub-processes with only variables. Probes will be added later as a natural extension. The guards 70, 71,.--,;n—1 Of the sub-process *{[Q — ho — Q(0)I .--lyna — An - II] are evaluated cyclically. This type of busy waiting may be implemented by +([Q —lro — Q(0) l--y¥o —+[y1 — Q(1) |nyt —? .ee [Yn-1 —_ Q(n _- 1) l-Yn-1 —* skip } J ] If a guard evaluates to true, the communication on @ is performed and the sub-process waits again for the probe of Q. The guards are reevaluated in order if all the guards evaluate to false since Q still holds. This guard sub-process may be decomposed syntactically in the same manner as any other process, creating a new sub-process for each guard 4; of the form: *[[Vi > lk Vin — Vi(0)]]] and a control sub-process of the form: Vt Q¢o) lo —> V} :[1 — Q(1) jo—...Vi_, [1 — Q(n-1) |\0 —> skip ] | | These sub-processes communicate through the n channels active V/(1,2) passive V;(2,1) ... channel (V/,V;) We do not create sub-processes for evaluating both 7; and 77. Instead, we evaluate one to either true or false. If y; is a simple variable z, the sub-process is *[[V — [zt > V(1)|-2 — V(0)]] 20 If +; is the negation of another cxpression 5, we perform the decomposition (passive U(2,1) ||Jactive U'(1, 2) *[[V — u!: [0 V(t — VOO)]]] )channel (U', U) If +; is the conjunction of two expressions 69 and 61, we use the following decomposition: (passive Uo(2, 1) *[[Uo —* [& — Uo{1)|-5 — Upo{0)]]] ||passive U,(2, 1) «[[F1 — [61 — Ui(1)|741 — 01(0)]]] ||active Ug (1, 2), Uj (1, 2) +[[V — Uf: [0 — V(0)|1 — UL: [0 — V(0)|1 — V(4)\/]] )channel (Uj, Uo), (U!, U1) By De Morgan’s rule, disjunction is similar to conjunction. By allowing probes in expressions, we can no longer be assured that the sequential evaluation of the expressions will result in a possible instantaneous evaluation of the cx- pressions. For example, the expressions 7X \ X might evaluate to true if the probe’s value changes between the first and second evaluation of the probe. We add extra circuitry to prevent this inconsistency. If any of the guards of the original guard set contain probes, we create a stable copy of the probe’s value before evaluating any of the guards. Each probe is evaluated and a stable copy is assigned to a variable each time though the busy-waiting loop. This insures the probe’s value is identical everywhere it is referenced in the guard set. Such an extreme procedure is not always required. We may save the extra variable used to store the stable value if the probe’s value is used only once in the guarded command set. In either case, it is sufficient to use the sub-process *[[V — KX > VOMbhxX — Vo) to evaluate a probe. 2.5 Example We illustrate some of the non-syntactic decompositions in of the priv? process in Figure 2.5 The sub-process +[[P — .. ]] is further decomposed into control and guard sub-processes. The guard sub-processes are created using the techniques for decomposing exclusive guard sets. The sub-process with the true expression is compiled similarly, except the control process forms an infinite repetition. The sub-process +|[H —> ...]] is split into sub-processes using the technique for non-exclusive guard sets. The guard process busy—waits to arbitrate between the probes of 70 and LO. The other decompositions performed in this phase but not shown in the figure are the division of the sub-processes which sequence three actions into two sub-processes each sequencing two actions. 21 s([P — [6 —s skip [Hb — 7); Pl] p (passive B(2, 1) *[[B A’ — B(o)]} || +{[B A -b — BG)]] |Jactive B'(1, 2) +[[P — B! : [0 — skip |1 — 7"; P]] )channel (B', B) +|[H — [U(0) — Kj]Z0) — Ki); H]|> (passive Ao(2, 1) ||passive A, (2, 1) +[[Ai A £(0) — Ax(1)] 41 A =Z(0) — Aj (0)]] ||passive C(2,1) active A}(1,2), Al (1,2) «[[C — Ag : [1 — C(0)]0 — Aj : [1 — C(1)|0 — skip ]]]] ||active C’ (1, 2) (FC! : fo — Kia — Ki]; HT )channel (c’, Cc); (Ap, Ao); (Ai, Aj) +([G — [true —> H';+];G]] Pp (passive D(2, 1) +#[[D A true — D(1)]] || +[[false —+ D(0)}] ||active D'(1, 2) [ED [1 — Fo — GI] )channel (D', D) Figure 2.5: Decomposition of the guards in the priv@ process Chapter 3 Compilations We have decomposed the original program into sub-processes which are now small enough to compile easily using the method described in [5,7]. We begin the description of the compilations by a brief review of this method and how it is applied to our problem. 3.1 Synopsis The compilation method consists of a sequence of step-wise refinements. Each process is transformed through a series of semantically equivalent yet increasingly more concrete forms until an implementable circuit results. In the first transformation, communications are replaced by explicit four-phase handshaking. We call the resulting intermediate form the handshaking expansion of the original process. In the next transformation, all explicit sequencing in the handshaking expansion is removed and the computation is represented by a set of simple guarded commands called a production rule set. By virtue of the way the set is constructed, certain invariant conditions hold for production rule sets, and thus they may be implemented in a race— and hazard—free manner as a collection of interconnected self-timed operators. The resulting operator sets may be used as a specification for a standard-cell implementation in VLSI. We now discuss each stage of the compilation procedure in more detail. 3.1.1 Handshaking Expansions The semantics of CSP requires that both processes involved in a communication complete the communication simultaneously. While we can not enforce “true” simultaneity in an asynchronous environment, it is possible define the simultaneous completion of a commu- nication action in a consistent and implementable manner (see [5]). Consider the following implementation of a communication from the active port X to the passive port Y, Each port is implemented by an input variable (denoted by ai for the port X) and an output variable (#0). A channel introduces a causal dependency between the output and input variables of the connected ports. The variables yz and xt are delayed copies of xo and yo, 22 23 respectively. The CSP communication Oz; X; ay; Y; Bz By where the a’s and ’s represent arbitrary commands is replaced by the four-phase hand- shaking expansion [o28]; Bs By With this implementation, just as with the CSP communication, the events 6, and fy can occur in either order, but neither #, nor #y can occur before az or ay. The four-phase protocol performs four one-sided synchronizations (denoted by the ver- tical bars) between the processes. Only the first two or the last two are strictly necessary for a synchronization. However, the others are used to reset the values of the handshaking variables allowing an identical implementation of each subsequent communication. In some cases, we may separate the synchronizations by moving part of the handshaking expansion to an earlier or a later point in the sequence. In general, this transformation, named reshuf- fling, may introduce deadlock. However, when applied to channels introduced by process decomposition, no deadlock is introduced and a very efficient implementation results. The handshaking expansion for a channel introduced by process decomposition az; zor; [i]; 20; Oy; [yi]; yor; nyt]; yol; a; B37 B *{[yi]; 85 yot; yt]; yo] || a; 20; [ai]; 201; [-28]; 7 may be reshuffled in three ways: *[[y¢]; (6,yoTs [>y¢]); yo] || 05 xo; [xi]; 20; [a8]; 7 *[[y#]; 8: yoTs [-y4]; yo] || a; eof; [x2]; (zo; [-27],7) *[[yt]; yots [-y@]; 8; yo] || (a, xo; [ai]); x0]; [>a]; 7 The notation S,T represents an arbitrary interleaving of the actions in the sequences S and T. (The ‘,’ operator binds less tightly than the ‘;’ operator.) Of these reshufflings, the first will be used most often in our compilations. 3.1.2 Production Rule Sets A handshaking expansion is transformed into a set of production rules each of the form G +— S where G is an arbitrary boolean expression and S is a simple assignment of true or false to a variable. A production rule set and its environment must ohey the stability and exclusiveness conditions. The stability condition states that for each production rule, if the guard G becomes true, it must remain true until the assignment S is performed. The exclusiveness condition states that no two production rules with the same output variable may simultaneously assign opposite values. The conditions may be used as the definition 24 @wae{ 2, L . (N=) Ny oo ah : “Ly (auV@=) ry ;3) >>: j@vCe= 4 Pky oF " aCe ¥ Figure 3.1: Production Rule Sets for Operators of race— and hazard-free circuits. With this restriction, we may now define an execution of a production rule set as the sequence of states starting at some initial state and where each subsequent state differs from the previous state by the execution of one production rule firing. A production rule set implements a handshaking expansion if each possible execution corresponds to a sequence of actions allowed by the handshaking expansion. Tn order to enforce this correspondence, state variables may need to be introduced into the handshaking expansion, and guards may need to be added or strengthed to certain assignments. 3.1.3. Operator Sets Operator sets are constructed by grouping together production rules with the same output variable and matching these rules with the definition of an operator. Variables may be arbitrarily inverted to facilitate the matching procedure. For our compilations, only the operators in Figure 3.1 are required. All references to an identical variable name must be implemented with the identical variable value. We call the implementation of this rule an tsochronic fork. 3.1.4 Extensions for Non-stable and Non-exclusive Program Constructs Production rule sets do not allow non-stable nor non-exclusive rules. However, the non- deterministic nature of the programming language introduces intrinsically non-stable or non-exclusive constructs. We introduce in Figure 3:2 two primitive processes which allow the implementation of non-determinacy. These primitive processes can not be represented in production rule set form, yet they both have practical implementations in VLSI. The primitive processes may still be interconnected. with circuits constructed from production rules at the operator set level. (Isochronic forks may be required.) 25 z > L> 4 | #[[gA « — ut; [og);u) q>z4s (q,2,y)S(u,o)= 4 lgAy— vt; [-a]; 0] y > Loy oy #[[2 — uf;[A2];u] (e,y)me(u,e)= 4 fy etif-ybed at ion y > > Figure 3.2: Primitive Process Definitions 3.1.5 Application to Our Problem Decisions need to be made at each stage of the translation procedure. Since a major design goal is to produce efficient circuits which are constructed from a very limited set of operator types, we choose a compilation style which follows these heuristics © We reshuffle communications when possible to result in implementations with the least number of state holding elements. # When state variables are required, we introduce one for each state in the original program. e We symmetrize production rules when possible to create symmetric combinational operators, such as the AND, OR, and wire operators. e If state holding elements are required, we symmetrize the production rules to form C elements. Such a compilation style can not always be applied top-down, that is by the blind application of rules at each stage of the compilation procedure. Some backtracking is required. However, the interaction between the compilation stages is justifiable in our case because the processes we wish to compile are small in size. 3.2. Communication Channels We use a four phase handshaking protocol to implement the general communication action. For channels which send data as well as synchronization information, we use more than the minimum two wires. Consider the channel declaration passive L(m,n) active R(n,m) ... channel (L, R) Such a channel is implemented by m+ n unidirectional wires using a unary encoding of the data. The n send wires of R correspond to the n receive wires of L. The active port 26 R initiates a communication action and thus these wires puint from AR to L. One of n values may be sent from R to L during the communication by raising exactly one of these wires. The m receive wires of R and the m send wires of L are also connected and similarly transit one of mn values from L to R. This communication channel may be described by the operator set: (i(¢)o)w(r(2)2) (0<i<m) (r(gjoyw(K}t) = (OS F< 2) Notice the notation used to name the wires of a channel. In the wire name I()o, the root I represents the port name, the suffix o represents this wire is an output of the port and the parameter in parenthesis represents which value corresponds to this wire. A suffix i signifies a wire as an input to a port. We allow the parameter in parenthesis to be a free running variable in order to concisely specify constructs of arbilrary size. Since there can be no ambiguity between a parameter and a suffix, we may without confusion use # as a free running variable. Using handshaking expansion notation(5], the general passive communication action (see Figure 1.4) may be written as [2(0)¢ —> I(z)oT; [-1(0)2];2(#)o0 1; ao} ....|l(n — 1)¢ —> I(a)ot; [7l(n — 1)4]; U()o |; an_4] and the general active communication as r(j)oT; [r(0)¢ — r(g)o]; [-r(0)2]; ao] ...|r(m — 1)4 — r(g)ol; [ar(m — 1)i]; am_1| (The parameters ¢ and 7 represent the oulpul: values of the communication on ports L and R respectively.) 3.3 Probe and Variable Values The value of the probe L(k) is implemented as the value on the single wire I(k)i. The values of boolean variables are also implemented as the value on a single wire. These values must be distributed to all the implementations of the sub-processes that use these probes and variables. We refer to these positions in. the circuit as usage points. Some technique is needed to insure that, after one of these values changes, every point in the circuit that references it receives the same value before execution is allowed to continue. For now, we assume the usage points are connected together by isochronic forks. The value of a probe or variable is defined to be the same at all usage points. In Chapter 4, we will discuss various implementations of these isochronic forks. 3.4 Compilations of Syntactic Forms Each of the sub-processes created in the last chapter is now compiled into self-timed circuit. 27 3.4.1 Parallel Composition Circuits are intrinsically concurrent entities. A collection of simple active communications may be implemented by separate circuits which perform single active communications after a global variable g becomes true: [9]; co; [et]; co |; [er] The value of g signifies whether the entire computation is going or reseting. We do not want an infinite repetition of communications, so a state variable is introduced into the handshaking expansion to distinguish when the communication has finished: [-2 A g]; cof; [et]; #1; [x]; col; [ee] The resulting operator set is (ci, true )C(zx) (g, 7) A(co) When g is false, co is false and every sequential process is inactive. All state variables of the system may be reset at this time. In particular, x is set to the initial value false . Raising g starts every sequential process simultaneously. 8.4.2 Skip Statement The skip statement has a very simple implementation. The process +[[D — skip ; D] is equivalent to infinitely repeating the communication action D. *[D] = »|[d#]; dot; [di]; do] The wire operator (di}w(do) implements this handshaking expansion. 3.4.3 Assignment Statement We must implement the sub-process «[[D — af; D[F — «|; Fl] Transforming into handshaking expansion form, we get «[[di > wt; [2];dot;[-di};do| |fé > wl; [52]; fot; [-F4]; fol] The derivation of the resulting production rule set, operator set and resulting circuit shown in figure 3.3 is straight—forward and given in [5]. We initialize the C element to the initializer declared in the program. 28 x di r> xf A diAz +> dof dt > ; adi r+ do| ~ D>. do fi > af finra > fof aft > fol (di, afi)C(z) (di, x) A(do) fo (ft, >) A(fo) fi> Figure 3.3: Compilation of Assignment Statement 3.4.4 Sequencing Sub-process Recall the definition of the sequencing process: «[[D — 8;T; D]] In the handshaking expansion for this process «|[d1]; sot; [si]; so]; [si]; tof; [té];t0 |; [44]; dot; [-di]; do |] the sequence dof; |-d:] may be reshuffled with the S$ communication +|[di]; 07; [si]; dot; [di]; so |; [-s2]; tot; [t2]; to]; [Ht]; dol] Introducing a single state variable z, +|[di]; sof; [st]; 1; [x]; dot; [di]; 90 ; [09]; 207; [te]; x |; [2]; 0; [02]; do |] we may now expand the handshaking expansion into a production rule set and equivalent operator set (see figure 3.4). We will use circuits similar to this in the implementation of guarded structures. We define the implementation of «[[D — skip ;T; D]] to be a new operator named a D element. (di, do)D(to,t?) = (di, at)C(x) (x, tt) \V (do) (di, z) A(to) 29 so st di r+ sot Fis v siAnt? rs af : aVts r+ dot ' adi tr sol asiAg tes tof ' tiAnst +> zi i mzVsi +> tol ' atiAae +--+» dol : (di)w(so) (si, att)C(x) (x, té)V(do) (81, x) A(to) di do Figure 3.4: Compilation of Sequencing Process 3.4.5 Control Sub-process By transforming the control process, #|[D —> P :[0 — So|...|k —> Sy; D|.- J] into a handshaking expansion, we get: *|[dt]; pot; [p(0)i — po; [-p(0}1]; 2(0)oT; [s(0)4]; #(0)o]; [-8(0)4] |p(&)i — pol; [>p(k)s]; s(k)ot; [s()3]; s(k)o |; [>8(k):]; dot; [di]; do} | As in the sequencing case, we may reshuffle the middle two actions of each D handshake to directly after the arrow and introduce a new state variable for each path. Tn general we may not reshuffle the communication P with the communication S. Delaying the comple- tion of P until after the initiation of a command which influences the guard set process connected to P potentially causes instability in the guard set process. The values of the state variables persist after the communication with P. We use these values to selected the 30 —u(O)A...Anu(k-1) Fe vo] au(k)A...A7u(n-1) +> dol av Ad pli)i A ~a(i) a(i) V s()s v s(i)t A ~p(i)é aa(i) V p(t w8(i)i A 2(1) #(j) Vv s(3)8 u(3) —p(j)i A 2(3) s(7)i A ~p(3)i (9) V plat —8(9)t A >2(9) PILIITIIITIIIItt) a(i)t u(t) vf po| s(t)oT z(i)| s(z)o| u(i) | (J) | u(z)t dot pol s(j)ot x(z) | s(j)ol pot > (O<i<k,k<j<n) u(9)t J Figure 3.5: Production Rule Set for the Control Process proper command sequence to execute. *[[di]; pot; [p(0)i — (0) T; [x(0)]; p04; [4p(0)s]; s(0)oT; [s(0):]; 2(0) |; [-2(0)]; s(0)o4; [>8(0)s| ln()s — x(k); [2(k)]; d(k)ot; [-4i]; po |; [=p(k):]; #(k)o 1; [o(k)s]; x(k) |; [-2(k)]; s(k)o|; [-s(k)i]; d(k)o| | The production rule set for this handshaking expansion is shown in Figure 3.5. Making use of the previously defined D elements, we get the simple operator set - (u(0),..., u(k — 1)) V(r) (u(k), . ++, u(n — 1))V(do) (di, =v) (po) (p(1)2, u{i))D (s(t)o, s(i)i) (O<i<k) (p(7)i, u(s))D(sG)o,sG)i) (KS 5 <n) 31 (Oo, yh D 0}t > rl 0°) s(1)o4 y s(1)é do <————_ p(i)t > a s(2)o~ y 9(2)8 D (2)1 > rl , 8(3)o4 y 9(3) D p(3)t > rl Figure 3.6: Circuit for Control Sub-process (k = 2,n = 4) An example circuit is shown in Figure 3.6. 3.4.6 Communication Actions We start the compilation of communication actions by considering the special case of only one usage per process. Simple Active The simple active communication *{[D —+ A(j) : [0 —> Sol... ]n —1 — Sp-1]; DI] may be implemented with a specific instance of the control process in the last section. In this case, no branch repeats, yielding the following operator set: (di)w(a(7)o) | (a(s), u(2))D(s(s)o, s(i})) (0<i<n) Figure 3.7 shows an example circuit. 32 Figure 3.7: Circuit for Active Communication (n = 3, 7 = 0) Simple Passive The simple passive communication sub-process has the non-reshuffled handshaking expansion: *([di]; [ lols) — plot; [p(s]; p@)ol; 8(7)0T; [s(7)2]; e(7)o1; [78 (7) 3 |; dot; [di]; do| 33 u(0)V...V u(m — 1) r+ p(ijot au(O)A...Asu(m—-1) +> p(sjol v(0)v....Vu(m— 1) -— dot av(0)A...Anv(m-1) +> dol di A p(j) > u(s)t uJ) An7s(7)i > ox(9) Tt mat A p49 )t + ulZ . su(j)AzGj) + sjjop ( <SF<™ s(7)iA-u(Z) +> _x(3) | a2(j)VuZj) +> a(s)ol as(g)tAn2(Z) > v(7)L | Figure 3.8: Production Rule Set for the Passive Communication Again, we reshuffle the middle actions of D aud introduce auxiliary variables. sl din p(j)i— u(9) 3 [uQ)]; p(*)oT, (x(a) 1; [z(a)]i o(s) 1; [v(9)]; €0T); [>di A -p(3)4]; u(3) 4; [-u(Q)]; p(i)ol, (s(9)oT5 [s(9)4]5 (9) Li 2); s(7)o]; [>8(9)¢]; (9) 1; [5e(9)]; dot) 1 The production rule expansion shown in Figure 3.8 produces this symmetrized operator set. (di, p(3)#)C(u()) - (ui), Lap c)ovs (j)4) (0<j<m) (u(0),...,u(m— 1))V(p(#)o) (v(0),.. v(m — 1))V(do) It is worthwhile to note that the C elements in these passive communication circuits provide the sole means of synchronizing the concurrent activities of the system. An oxample circuit is shown in Figure 3.9. 34 nN D p(1)i >—(¢) >—_ ! > a(2)o h Y 9(2)s h D p(2)i >—(c) >— |! > di >— do < Figure 3.9: Circuit for Passive Communication (n = 3,1 = 0) 35 Multiple Usages of Passive Ports Since communications on a particular channel may be performed in several different sub- processes, we must produce a means sharing the use of these channel among the various sub-processes, We expand the simple passive communication to allow several sub-processes to respond and complete a communication on the same port. We use a “passive to multiple active port” converter with no buffering capacity to implement this expansion. Let P be the single passive port and Ag,A1,...,Az—1 be the k active ports of the converter. The active ports pair up with the passive ports of sub-processcs. When one of the input wires of the passive port is raised, the corresponding output wire is raised in each of the k active ports. Because no two sub-processes operate concurrently, only one of the active ports A(é) will respond to the communication by raising an input wire a(i)(j)i. (Notice the use of double parameters to name the wires of the multiple active ports.) The converter will then raise the corresponding output wire of the passive port p(j)o, resulting in the lowering of the initiating input wire of P and then the lowering of the corresponding oulpul wires of each of the k& active ports. We assume until a refinement is given in Chapter 4 that the corresponding output wires of the active ports are connected via isochronic forks. The conumunication action Lhen continues when the single input wire a(j)(?)i lowers and finally completes with the lowering of output wire p(j)o. We may use the operator set p(l)¢ = a(s)(2)o (O<i<k,O<£<n) (a(0)(3)#, a(1)(a)¢,...,a(& — 1)(9)1) Vp@)o) = (OS << m) to implement this passive to multiple active converter. The = operator allows two different names to represent the same variable. An example circuit is shown in Figure 3.10. Multiple Usages of Active Ports In the case of several sub-processes calling a single active port, we use a multiple passive port to single active port converter called a merger. Let Po, P,,...,P¢-1 represent the k passive ports and A the single active port of the converter. The passive ports of the converter are paired with the active ports of the sub-processes. A communication through an active port of a sub-process is transparently converted into a communication on the active port A. The converter must store which passive port initiated the communication in order to direct the acknowledgement of the communication back to its source. The following operator set specifies an implementation of such a converter: (7(0)(5)é,n(4)(/)i, ... p(k - 1)):) Vaso) (OS j < m) (p(i)(0)i, p()(1)é,..-,p)(m— Ii) V(uG)) (OX <&) (u(t), a(s)})C(()G)o) (OS 1< k,O< 5 <n) The double parameters specify port number and value number, respectively. An example circuit is shown in Figure 3.11. 36 p(0)i > > a(0)(0)o p(l)i > > a(0)(1)o p(2)i > > a(0)(2)o <€ a(0)(0)i < a(0)(1)i 5 L—> a(1)(0)o P(0) > a(t)(1)o > toe b—————< a(1)(0) Ae<—C (— < a(t)(ayi Figure 3.10: Passive k — (m,n) Expansion Circuit (k = 2,m=2,n= 3) p(0)(0)i > p(0)(1)i > p(0)(2)¢ > C Y H(0)()o<—}-(o)— a) p(0){2<——{c }- » p(1)(0)i > p(1)(1)'> (1) (a> y) Hl1)(e<—-(c) p(1)(1)o a(0)o t A a(0)i a(1)i df A Figure 3.11: Active k — (m,n) Merger Circuit (k = 2,m = 8,n = 2) 37 3.4.7 Exclusive Guards The sub-process #[[QAzoA...Atp-1 A 70K A..-ATtn-1 — Q(8)]] may be implemented simply with an n + 1 input AND gate. (qt, @0, ++) 2k-1, "Lk + aan—1) \(a(¢)o) 3.4.8 Non-exclusive Guards The sub-process *[[Q — |e — Q(1)|-2 — 00) may be implemented with two 2 input AND gates. If probes are used, we need to implement the process *{[Q — [X(k) — Q(1)IH-X(k) — O(0)]]] By expanding this process to its handshaking expansion, *|[gt At(k)i — g(1ot; [5¢1]; ¢(1ol lat A -a@(k)é —+ g(O)oT; [92]; g(O)o | we see that. it matches the synchronizer process defined earlier if we use the instantiation (qt, (k)t, -a(k)t)S(q1o, gOo) The and, or, negation, and busy-waiting sub-processes all have trivial implementations after reshuffling. Both the and and the or sub-processes are implemented with a single OR gate. The negation sub-process merely interchanges two wires. We use the busy-waiting sub-process as an example of the reshufflings performed on these sub-processes. Consider the simple sub-process *[[Q — U :[0 + V : [0 — skip |1 — Q(1)] [1 — QI] Tn handshaking expansion form, *([qi]; uot; [u(O)i —+ uo]; [ru(0}]; vot; [v(0)i —> vo]; [>v(0):] \v(1)4 — vo]; [>0(1)]; got; [92]; eo \u(1)¢ —> ual; [—u(O)¢]; g(0)ot; [94]; ¢(0)o} 38 The U and Q communications may be reshuffled together arbitrarily because they are both communications introduced by process decomposition. *[ [gi]; uot; [u(O)é —> vot; [v(O)é —+ uo]; [-u(0):]; vo]; [-v(0)F] lv(1)§i— g(1)ot; [44]; uo]; - [pu(0)¢]; vo]; [v(1)9]; g(1)o} ] or — 4(0)oT; [99]; uo}; [-u(0)s]; (1) The resulting operator set is (q2, =v(0)#) A(uo) (u(0)4)w(vo) (u(1)i)w(9(0)o) (v(1)é)w(4(1)o) 3.5 Example Figure 3.18 shows the compiled circuit corresponding to the priv example. 39 <8 yy gi> g > =D q(O)o Figure 3.12: Exclusive Conjunction Figure 3.13: Simple Variable x V : u i —————>v(1)o +—> ¢q(Lo ' ' > 5 vt »— v benuul y +—>> q(0)o __¢ Figure 3.14: Simple Probe Figure 3.15: Conjunction vt , Oil ray v(i)o : r ’ r—>q(1)o Figure 3.16: Disjunction Figure 3.17: Busy Evaluation 40 Ad A | AY Vv “a AVY v Figure 3.18: Complete Circuit for priv0 Process Chapter 4 Isochronic Forks In the previous chapter, we implemented the use of probes and variables at different points throughout the circuit by postulating the existence of an isochronic fork which distributes the value of a probe or variable to all usage points instantaneously. This isochronicity assumption of a fork is valid if the usage points are close together. However, locality of usage points can not be guaranteed unless some hound is placed on the size of the sequential processes from which the circuits are generated. We place no such bound on the sequential processes defined in our source language. In this chapter, we discuss methods of realizing large isochronic forks as well as alternate methods of implementing certain constructs of the language in order to avoid the need for large isochronic forks. 4.1 Electrical Solution We may implement isochronic forks local to a single chip by connecting the usage points together with a low resistance interconnect, typically either metal/ or metal2. With present technologies, the delay in changing the potential of a usage point two chip widths away from its source is still significantly less than the delay in an ordinary operator as long as these long wires are driven with optimally sized inverter horns. However, in future technologies, interconnect delays will become more significant.and the isochronic fork assumption may be invalid [1]. Fortunately, arbitrary-size isochronic forks are not intrinsically necessary for our compilation strategy. We may algorithmically reduce each large isochronic fork into an isochronic fork between two usage points. 4.2 Algorithmic Solution The isochronic forks produced by the compilation methodology are local to a single sequen- tial process. We modify each sequential process so that when it changes a (circuit) variable which must isochronically fork to several usage points, it suspends until all usage points have received the change. Only after the process detects that the variable’s new value has 41 42 (z)w(A) (A)w(B) (B)w(C) (C)w(D) , (V)w(2) > Figure 4.1; Distribution and Detection Using a Linear Ordering reached all usage points can execution resume. We split the description of how to modify our existing implementation into two parts: e We describe how to distribute a variable’s value to all usage points in such a way that we can detect when all points have reach their new values. Furthermore, we use isochronic forks with ouly two oulpuls in this implementation. e We describe the changes needed to the previous implementations of the language con- structs to suspend the process until the fork has completed distributing the variable’s value. 4.2.1 Variable Distribution and Completion Detection We detect that a variable’s value has been distributed to all usage points by observing the value of a new circuit variable called a completion signal. Assume we must distribute the circuit variable x to the usage points A,B,C and D. If we introduce the completion signal and connect z to A, Ato B, B to C, C to D and D to é with wire operators, we can be assured that. when @ changes, the change has already propagated through all the intermediate usage points. In so doing, we have reduced the large isochronic fork to several binary isochronic forks, Thus, we may use the circuit shown in Figure 4.1 to distribute and detect distribution of an isochronic fork. Instead of linearly ordering the usage points, we may send separate wires to each point and construct the completion signal using a tree of C operators. (see Figure 4.2) The output of such a tree changes when all its inputs have changed and may be used in exactly the same fashion as the completion signal of the above linear ordering. 4.2.2 Process Suspension The previous implementations of the active channel merger, the passive channel expansion, the passive communication and the assignment constructs are sources of isochronic forks 43 (z)w(A) (z)w(B) (z)w(C) (z)w(D) (A)w(4) (B)w(éz) x (C)w(c) (D)w(ép) (24, 2p)C(Zap) (2c,%p)C(&cp) (4B, €cp)C(#) & ©> IAARE Figure 4.2: Concurrent Distribution and Detection between (potentially) more than two usage points. We modify these implementation to wait for the completion signals of the forked variables. The k-way isochronic forks needed in a k-way active channel merger may be reduced to 2~-way isochronic forks by using trees of 2-way active channel mergers. The remaining large isochronic forks (only if the number of input values is greater than one) are eliminated by the circuit shown in Figure 4.3. The M block in the circuit merges together m one-output and one-input value channels. This block may be implemented without large isochronic forks. The completion signals for the forks p(0)(*)¢ and p(1)(*)¢ must change before an output value changes. Passive communications and passive channel expansions are modified as shown in Fig- ures 4.5 and 4.4. The completion signals for the input variables must change before the flow of control is transfered to the next statement. The synchronization is introduced before the calls to the statements S$;, ensuring the correct valuo of the input variables inside the implementations of these statements. The modified assignment implementation (see Figure 4.6) uses the completion signal instead of the variable value to detcct when the assignment has finished. 44 B(0)(*)é A(1)(+)é p(0)(0)i > p(0)(1}¢ > p(0)(2)i > rl) TY p> alee p(0)(0o <— b-(,) Ea > a(i)o p(0)(1)o é —> a(2)o p(1)(0)i > p(1)(1)i > p(1)(2)i > p(1)(+)i p(1)(0)e <—_ a(0)i p(i)(1)o< < a(l)i OC Figure 4.3: Modified 2 — (3,2) Active Merger p(0)o SYNC s(0)o AY s(0)¢ D p(0)é » (6) pH—>—1 | > a(l)o AY (1)i AN 3— (1,1) D | M a(2)o h Y a(2)é NN D p(2)é >—(c) —>—— | __>— da >— do mo di Figure 4.4: Modified Passive Communication 46 p(0)i> > a(0)(O)o p(1)i> > a(0)(L)o v(2)i> > a(0)(2}o < a(0)(0): —<€ a(0)(1)i ° > a(1)(O)o p(ojox—€ > a(1)(1)o H————=> a(1)(2)o |_____« , a(1)(0)i (1)o pi synoot_| ° —<CE < aes p(l)i synout_| , | Figure 4.5: Modified 2 — (2,3) Passive Expansion La <@ & Ps di> i “D>. o i> = Daa Figure 4.6: Modified Assignment Chapter 5 Circuit Optimization The circuits generated by the techniques of the last chapters are functionally correct but some inefficiencies have been introduced by the generality of the procedure. The composing rule for each language construct is strong enough to avoid interaction between arbitrary commands. Better circuits may be synthesized if these interactions are considered in more detail. In particular, when commands do not interact, a more simple implementation of the language construct may be used. We consider some of the important special cases. 5.1 Removing D-elements The most useful optimization is the removal of unnecessary D-elements. The removal of sequencing operators corresponds directly to reshuffling the handshaking sequences of the adjacent commands. Replacing the operator (s¢,s0)D(to,ti) with the two wire operators (si)w(to) and (¢i)w(so) intertwines the handshaking expansion of the passive communica tion S and the active communication T yielding: [s#]; tof; [t4]; sof; [582]; to |; [#7]; so] We may remove D-elements in cases where the above reshuffling does not destroy the original semantics of the program. In the general case of the control structure process, D-elements are required between each guard and the sequence of statements that follows it. The D-element may be removed if the sequence of statements does not change the value of any guard in the guarded command set. A trivial example is a guard followed by the single statement skip. The statement skip can not change the value of any guard. Assignments are also easy to characterize. If a simple assignment to the variable z immediately follows a guard, the D-element. may he removed if the assignment to + does not change any guard. 47 48 az Adi ++ sof di A st > «ft adiVe ++ sol tAn7st r+ tof te r— dot adi N-si +> al siV aa r+ tol ati + dol (di, si)C(x) (—24, z)A(¢o) (t¢)w(do) di do . Figure 5.1: Another Sequencing Circuit 5.2 Sequencing Operators By reshuffling the sequencing process +[[D — $;T; D]] in a different way than in the last chapter (Page 28) #|[d#]; sof; [st]; so]; [82]; tof; [t#]; dot; [d1]; to]; [582]; do |] we gel a different circuit made of wires and a so-called Q operator (Figure 5.1). We call the operators D and Q sequencing operators. Sequencing may be performed by arbitrary trees of sequencing operators, not just the linear chains described in Chapter 2. (The Q operator may not be used to replace the D operator in the control and communication sub-processes.) By manipulation of these sequencing trees, smaller implementations of the control flow are possible. Sequencing operators may be factored through active channel mergers if the sequencing operators are of the same kind and never active at the same time. If an action is common to the last action of two or more selection branches, the active merge process may be replaced by asimple OR gate. We do not need a full merger process because regardless of which branch initiated the action, control will continue with the same action. 5.3 Passive Channels The special form +[D — 8; D]] 49 60 Figure 5.2: Comparison of Passive Communication Implementations where S does not call the communication D, may be implemented simply as a pair of wires. This implementation is superior to the standard implementation requiring one C, one D and one A element (Figure 5.2). A user programmed passive communication may be im- plemented with wires if the compiler is able to prove that the passive communication is only performed as the very last action of an continuing repetition. Such passive commu- nications do not introduce concurrency. This implementation involves a reshuffling of the handshaking expansion: +([di]; sot; [st]; so]; [584]; dot; [dz]; do |] The middle action and wait of the D handshaking protocol are moved forward. +[[ds]; 801; [st]; dot; [ds]; 20 |; [81]; do |] The process commits to finishing the D communication before S is finished. The commu- nication S must not start a separate communication on port D. Otherwise, the two D communications would have non-exclusive access to the same channel. The reshuffling can only be performed if the communications on the active port connected to D are not reshuf- fled. In the method presented here, we never reshuffle user specified active communications. The control structures of the more complicated guarded command «[[D A Go — So; D| ves IDAGn-1 — Sr-1} D]| where the G; are conjunctions of possibly negated variables, may also be implemented directly as wires as long as D is not called in any of the S;. To reshuffle the even more general form with different passive probes, +#([DA Go — S; DIEAG, — T; E]] 50 the communication T must not raise the probe of D and 9 must wut raise the probe of FZ. Optimizations also exist for repetitive structures with guards the conjunct of positive probes. For instance, *[[D AF — S$; D;T; F]] may be reshuffled to +([di A fi]; sof; [sz]; dot, fot; [di A aft]; so |; [88]; do |, (to7; [t#];¢0 |; [ts]); fol ] This reshuffling has a simple implementation (Figure 5.3) (di, fi)C(so) (st)w(do) (st, fo)D(to, tt) 5.4 Special Circuits for Arbitration In special cases, efficient arbitration circuits may be used to implement non-exclusive guards. Both passiveU,Z activeS,T process arbiter(U, £,S,T) and passive Q(2, 1) _ *[Q AT — Q()IQA L — Q(i)]] process enabled_arb(Q) may be implemented without busy waiting. In the first case we use the arbiter from [6]. (ui, 2)me(u, 1) (u,~t4) A(6o) (1, -6i) A(to) (st)w(uo) (ti) w{lo) The. me operator is a primitive process which implements the handshaking expansion (uz, v7)me(uo, vo) = +[[ud —> uot; [sus]; uo | ut —> vot; [rv]; v0 |] as long as the four-phase protocol is obeyed on ut, uo and vi, vo. The second case, after handshaking expansion, is an instantiation of the synchronizer primitive process: (g2, 27, 14)S(q(1)o, 9(0)o) When the enable signal qi is raised, this element behaves like a standard mutual exclusion operator. However, when gi is low, both outputs remain low. 51 80 ¢f =to tt Vv a Y uo < < st di fe) do < . fo < lo < €< te Figure 5.3: Reshuffled Circuit for Mul- tiple Passive Communications Figure 5.4: Non—busy-waiting Arbiter 5.5 Example We apply these optimizations to the priv0 circuit produced in the last chapter. The arbiter process is used instead of the busy-waiting implementation of the guard set in the main process. The redundant D operators sequencing skip statements are also removed. The communication R dees not cffcet the guards 6 and —) and thus the sequencing operators corresponding to the arrows in thé procedure may be removed. No statements in the procedure influence the guards of the main process and thus no sequencing element is needed to implement the arrows of that selection statement either. The sole sequencing remaining separates the procedure call from assignment to the variable b. By manipulating the sequencing tree for both paths through the main selection statement, a sequencing operator may be factor though the merger for the procedure call. After these optimizations, only one sequencing element remains. The resulting circuit is shown in Figure 5.5. This circuit corresponds exactly to the best circuit produced by hand compilation. 52 VA VY oS A A Y Vv Vv AV An nN Figure 5.5: Optimized Circuit for the priv@ Process Conclusion We have produced a working automatic compiler that implements a subset of the translation techniques described in this thesis. This compiler closely follows the structure of standard source—to—machine code compilers, in particular the Prolog implementations described in [10,11]. While it is beyond the scope of this thesis to describe the compiler in detail, we will make claims about its performance, and thus make claims about the quality of the circuits produced by the compilation technique as a whole. While many criteria make up the quality of a circuit, we will restrict our attention to the size of the resulting circuit, defined in terms of the number of gates or the number of transistors needed to implement it. , The circuits produced by the compiler are slightly larger than those produced by di- rectly applying Martin’s method. The compiler does not introduce state variables between arbitrary actions in the handshaking expansion of the process, nor does it always introduce the minimal number of these variables. The compiler is handicapped in this sense. How- ever, the optimal introduction of state variables is a hard problem and solutions to it will be tractable only for small programs. The compiler produces good solutions, yet they are not always optimal. We claim the solutions are good because we can prove that a circuit produced by the compiler is no larger than a constant times the size of its corresponding input description. The proof follows from that fact that each program is decomposed into a number of sub- processes proportional to the number of constructs in the program, and each resulting sub-process has a constant sized implementation. (For this statement to be true, we may not use the exclusive guard set technique described in Section 2.4.3 because of the possible exponential blow-up when representing an arbitrary boolean function in disjunctive normal form. However, the non-exclusive guard set technique of Section 2.4.4 may be used in its place.) We can not expect a better asymptotic growth rate for our compiler. We have compared scvcral medium sized designs produced by hand at Caltech with designs produced by the compiler. e 3a +1 Engine (Tony Lee) e Systolic Multiplier (Pieter Hazewindus) e Bit-serial Routing Automata (Steve Burns) 53 54 e Lazy Stack (Alain Martin and Steve Burus) e Ring of Mutual Exclusion (Alain Martin and Andy Fyfe) The results vary: the compiled designs being no more than three times as large as the hand designs and in some cases smaller than the hand designs. The variability is due mostly to difficulties in specifying efficiently the algorithms used in the hand designs in our source language. In summary, the compilation procedure described in this thesis represents a complete, systematic method for translating an arbitrary concurrent program into a self-timed circuit. Furthermore, the circuits produced are of high quality. The size of a constructed circuit is no larger than a constant times the size of the input specification. Also, the translation mechanism mimics that used in standard source code to machine code compilers, and thus compiler theory can be applied to construct a working translator. Bibliography [1] M. Annaratone, Digital CMOS Circuit Design, Kluwer Academic, Boston, pp 134-5 (1986) [2] E. W. Dijkstra, “Guarded commands, nondeterminacy, and formal derivation of pro- grams”, Comm. ACM 18, 8, pp 453-457 (August 1975) [3] C. A. R. Hoare, “Communicating Sequential Processes”, Comm. ACM 21, 8, pp 666- 677 (August 1978) [4] A. J. Martin, “An Axiomatic Definition of Synchronization Primitives”, Acta Infor- matica, 16, pp 219-235 (1981) [5] A. J. Martin, “Compiling Communicating Processes into Delay-Insensitive VLSI Cir- cuits”, Distributed Computing, 1, pp 226-234 (1986) [6] A. J. Martin, “A Delay-Insensitive Fair Arbiter” , Caltech Computer Science Technical Report 5193:TR:85 (1985) [7] A. J. Martin, “The Design of a Self-Timed Circuit for Distributed Mutual Exclusion” , Proc. 1985 Chapel Hill Conf. VLSI, ed. Henry Fuchs, pp 247-260 (1985) [8] A. J. Martin, “The Probe: an Addition to Communication Primitives”, Information Processing Letters, 20, pp 125-130 (1985) 9| C. L. Seitz, “System Timing”, Chapter 7 in Mead and Conway, Introduction to VLSI » ¥y Syetemo, Addison-Wesley, Reading MA (1980) [10] L. Sterling and E. Shapiro, The Art of Prolog, The MIT Press, Cambridge MA (1986) [11] D. Warren, “Logic Programming and Compiler Writing”, Software-Practice and Expe- rience, 10, 2 (1980) 55