Slack Matching Citation Prakash, Piyush (2005) Slack Matching. Master's thesis, California Institute of Technology. doi:10.7907/g43p-hv51. https://resolver.caltech.edu/CaltechETD:etd-05272005-134017 Abstract In this thesis we present a method for slack matching asynchronous circuits, described as a collection of handshaking expansions. We present an execution model for a restricted class of HSE. We define the number of messages that a process contains. The static slack, dynamic slack and dynamic threshold are defined. We state sufficient conditions under which the dynamic slack of a pipeline of half-buffers is the sum of that of the processes comprising the pipeline. The slack matching problem is formulated as that of ensuring that all pipelines and rings in a system can simultaneously contain a number of messages that is no less than the dynamic threshold but no greater than the dynamic slack. We describe an algorithm to formulate the slack matching problem as a mixed integer linear program. Item Type: Thesis (Master's thesis) Subject Keywords: asynchronous; slack elasticity Degree Grantor: California Institute of Technology Division: Engineering and Applied Science Major Option: Computer Science Thesis Availability: Public (worldwide access) Research Advisor(s): Martin, Alain J. Thesis Committee: Unknown, Unknown Defense Date: 26 May 2005 Record Number: CaltechETD:etd-05272005-134017 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-05272005-134017 DOI: 10.7907/g43p-hv51 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 2151 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 02 Jun 2005 Last Modified: 16 Apr 2021 23:24 Thesis Files Preview PDF - Final Version See Usage Policy. 295kB Repository Staff Only: item control page

Slack Matching Thesis by Piyush Prakash In Partial Fulfillment of the Requirements for the Degree of Master of Science California Institute of Technology Pasadena, California 2005 (Submitted May, 2005) c 2005 Piyush Prakash All Rights Reserved ii Acknowledgements I wish to thank my advisor, Alain Martin, for his guidance and encouragement. I also thank the members of the Asynchronous VLSI group at Caltech for the stimulating discussions: Mika Nyström, Catherine Wong, Karl Papadantonakis, Wonjin Jang, Jonathan Dama and Paul Pénzes. Last but not least, I wish to thank my parents for their support and encouragement. The work described in this thesis was sponsored by the Defense Advanced Research Projects Agency and monitored by the Air Force Office of Scientific Research. iii Abstract In this thesis we present a method for slack matching asynchronous circuits, described as a collection of handshaking expansions. We present an execution model for a restricted class of HSE. We define the number of messages that a process contains. The static slack, dynamic slack and dynamic threshold are defined. We state sufficient conditions under which the dynamic slack of a pipeline of half-buffers is the sum of that of the processes comprising the pipeline. The slack matching problem is formulated as that of ensuring that all pipelines and rings in a system can simultaneously contain a number of messages that is no less than the dynamic threshold but no greater than the dynamic slack. We describe an algorithm to formulate the slack matching problem as a mixed integer linear program. iv 1 Introduction Asynchronous circuits are designed as communicating modules that use local handshakes instead of a global clock for synchronization. It has been observed that the cycle-time of an asynchronous system can be lower than that of the slowest module in the system running on its own. Slack matching is a technique to reduce the system’s cycle-time by inserting buffering into communication channels. Slack matching is only guaranteed to be safe on systems that are slack elastic, i.e., systems such that an arbitrary amount of buffering can be added along any communication channel without affecting the correctness of the system [5]. Slack matching has been compared to the retiming problem in synchronous design. Whilst retiming can be applied to asynchronous systems with good results, the results are inferior to optimal slack matching. Slack matching has been shown to be NP-complete [2] whereas retiming for optimal throughput can be solved in polynomial time [3]. We reduce slack matching to optimizing a given cost function over a set of linear constraints, with some variables restricted to being integers. When the cost function is linear in the number of slack matching buffers added, mixed integer linear programming (MILP) solvers can be used to slack match a system. Systems are often designed with a target cycle-time, τ0 . We will study the problem of adding buffers to a slack elastic system to reduce the overall cycle-time of the system to τ 0 . The processes in the system will be restricted to using each communication channel exactly once per cycle. The systems will be described at the handshaking expansion (HSE) level, with the HSE annotated with delays. 1.1 Prior work Chapter 2 of Lines[4] studies asynchronous pipelines and introduces the concept of dynamic slack ; however Lines does not rigorously define dynamic slack. Pénzes[9] presents an execution model for production rule sets. Using this model, the slack matching problem is formulated as an integer linear programming problem. However, no explicit algorithm is given to generate the integer linear program. No comment is made on the size of the integer linear program generated relative to the size of the system being slack matched. Chapter 5 of Wong[10] presents a method for slack matching systems composed of processes with the PCHB reshuffling. If the delays of all processes are identical, the slack matching algorithm presented is similar to that presented here. However, for heterogenous systems Wong[10] determines the dynamic slack of a pipeline of buffers by analyzing all paths in the pipeline. In contrast, we will state conditions under which the dynamic slack of a heterogenous pipeline is the sum of the dynamic slack of the components of the pipeline. This allows us to construct a smaller integer program in polynomial time for the slack matching problem. 1 1.2 Outline We first describe an execution model for HSE called constraint graphs. We will state restrictions on the class of HSE that can be modeled by constraint graphs. We define the number of messages in rings and pipelines. We study how changing the number of messages in a system affects its constraint graph. The concepts of static slack, dynamic slack and dynamic threshold are defined. We present sufficient conditions under which the dynamic slack of a pipeline of half buffers is the sum of that of the processes comprising the pipeline. The slack matching problem is formulated as that of ensuring that it is possible for all pipelines and rings in a system to simultaneously contain a number of messages that is no less than the dynamic threshold but no greater than the dynamic slack. An algorithm is described for generating a set of linear constraints that need to be satisfied in order to slack match a system. The performance of the algorithm on circuits from the Lutonium[7] and MiniMIPS[6] is discussed. 2 Execution Model—Constraint Graphs We first describe the constraint graph execution model and then provide an algorithm to generate the constraint graphs of a restricted class of HSE. 2.1 Constraint graphs Definition 1 A constraint graph is a 4-tuple C=(V, E, k, δ) where • V is a set of vertices • E, the edge set, is a set of ordered pairs of vertices • k : E → {0, 1} specifies the initial token placement • δ : E → [0, ∞) is the delay function Constraint graphs are used to model repetitive systems. The vertices of a constraint graph represent events, and the edges capture the partial ordering between events. An edge (u, v) will have a token when event u has occurred but the subsequent occurrence of event v has not yet occurred. The delay, δ(u, v), of an edge is the minimum delay between an occurrence of u and the subsequent occurrence of v. Tokens move through the system per the following rule: when all the fan-in edges of a vertex contain and token, and for each such edge (u, v), the token has been on the edge for at least δ(u, v) time, a token can be removed from all the fan-in edges and placed on the fan-out edges of the vertex. 2 2.1.1 Executions of a constraint graph An execution of a constraint graph (V, E, t, δ), is any function, e : V × N → [0, ∞) such that ∀i ∈ N, (u, v) ∈ E : e(v, i + k(u, v)) − e(u, i) ≥ δ(u, v) e(v, 1) = 0∀v : ∀(u, v) ∈ E : k(u, v) = 1 e(u, i) denotes the ith occurrence of the event u. Consider the mapping le ((u, v), t) : E × [0, ∞) → {0, 1} to evaluate to 1 when there is a token on edge (u, v) at time t in execution e. le ((u, v), t) is defined as: le ((u, v), t) = ∃i : e(v, i + k(u, v)) > t ∧ e(u, i) ≤ t A linear execution is an execution, where for all u, e(u, i) = αu + pu · i. αu and pu are, respectively, the offset and cycle period of the vertex u. If two vertices u and v appear on the same cycle in the constraint graph, pu must equal pv . The cycle time, τ , of a linear execution of the constraint graph (V, E, k, δ) is defined as τ = max{pv }. (1) v∈V In the remainder of this thesis, we will only consider systems such that their constraint graphs are strongly connected. Chapter 2 of Burns[1] defines repetitive Event-Rule (ER) systems. An execution of a constraint graph is analogous to a timing function of a repetitive ER system. Similarly, the fastest execution and fastest linear execution of a constraint graph are analogous to the timing simulation and minimum-period linear timing function of an ER system. Burns[1] shows that there exists a timing simulation of an ER system if for all cycles c in its collapsed constraint graph, either the sum of the occurrence index offsets along the cycle is greater than zero or the total delay along the cycle is zero. Burns shows that there exists a minimum-period linear timing function of a repetitive ER system whenever the timing simulation exists. Let s and s 0 represent the timing simulation and minimum-period linear timing function of a repetitive ER system, (E,R). It can be shown that there exists a finite B such that ∀u ∈ E, i ≥ 0, s0 (u, i) − s(u, i) ≤ B when the collapsed constraint graph of the ER system is strongly connected. Similar arguments can be used to demonstrate the existence of a fastest execution of a constraint graph if for all cycles c in the constraint graph: X k(u, v) = 0 ⇒ (u,v)∈c X δ(u, v) = 0. (2) (u,v)∈c It can be shown that fastest linear execution exists whenever the fastest execution exists. Let e and e 0 be 3 the fastest execution and the fastest linear execution of the constraint graph. Then there must exist a finite B such that ∀u ∈ V, i ≥ 0, e0 (u, i) − e(u, i) ≤ B. Therefore, the cycle period of a vertex u in the fastest linear execution of a system is the mean time between successive occurrences of u in the system’s fastest execution. The fastest execution and fastest linear execution of a constraint graph can be constructed in the same manner as the timing simulation and minimum-period linear timing function of an ER system are constructed. The arguments in Burns[1] can also be used to show that the cycle time, τ , of the fastest linear execution of a constraint graph is given by τ= max all cycles c  delay along cycle c # of tokens on cycle c  . (3) Only simple cycles, i.e., ones that do not have any sub-cycles, need to be considered in the maximization. 2.2 Repetitive straight-line handshaking expansion In this section, we define a class of HSE that can be modeled with constraint graphs. An HSE in which each select statement is of the form [G → skip] (a wait), where G is a conjunction of literals, and each repetition statement is of the form ∗[true → S] (a non-terminating loop) is said to be a straight-line-handshaking-expansion(SLHSE) [1]. Constraint graphs will be used to model systems that are described as repetitive SLHSE in standard form. An SLHSE that satisfies the following restrictions is said to be a repetitive SLHSE in standard form. 1. Each process can be written as P ≡ S; ∗[T ]. 2. S and T are sequences of alternating waits and assignments that begin and end with a wait. 3. Each variable is either only assigned and used in one process or is used to implement a communication channel. A pair of variables (a, b) implement a communication channel if a is assigned only by one process P , b is assigned only by one process Q, and P and Q are the only processes that use the variables a and b. Furthermore, the assignments to a and b obey a four-phase handshake protocol. 4. If a variable appears in a wait statement, then the variable is either a local variable or the input variable of a communication channel such that this process is the one that assigns the corresponding output variable. 5. There are no vacuous assignments or vacuous waits on variables. However all variables are initialized. 6. All assignments occurs at most once in S and exactly once in T . 7. The projection of T onto the statements in S is S. 4 8. For all assignments a such that a appears in S, if a; a0 appears in the projection of T onto {a, a0 }, a0 appears in S. 9. For all variables w such that [f (w)] appears in S, all assignments a such that [f (w)]; a appears in the projection of T onto the variables {w, a}, also appear in S. Restrictions 1–5 can be satisfied by rewriting an SLHSE. Conditions 6–9 ensure that the system is repetitive and can be modeled by a constraint graph. Example 1 The process: PCHB ≡ init; lo↑; [ri]; ro↓; [¬li]; lo↓; *[[¬ri ∧ li]; ro↑; lo↑; [ri]; ro↓; [¬li]; lo↓] init ≡ lo↓, ro↑, [¬ri ∧ li] can be rewritten as a repetitive SLHSE in standard form: PCHB ≡ init; [true]; lo↑; [ri]; ro↓; [¬li]; lo↓; [true]; *[[¬ri ∧ li]; ro↑; [true]; lo↑; [ri]; ro↓; [¬li]; lo↓; [true]] 2.3 Constructing constraint graphs of an HSE We now describe how to construct the constraint graph of collections of repetitive SLHSE in standard form. • Vertices: For each variable v, create vertices labeled v ↑ and v ↓. These vertices represent v being assigned the values true and false respectively. • Edges: The edges of the constraint graph capture the partial ordering between assignments in a collection of HSE. Consider an assignment, a, in T , such that at least one assignment precedes a in T . We can rewrite T as T 0 ; a0 ; w; a; T 00 . w and a0 are respectively the constraining wait and constraining assignment of a. Consider an assignment, a, such that no other assignment precedes a in T . Rewrite T as w1 ; a; T 00 ; a0 ; w2 . In this case the constraining assignment of a is a0 and w1 and w2 are the constraining waits of a. For every assignment a, construct edges (u, a) for all u such that either u is a constraining assignment of a, or u is an assignment that can make a literal in a constraining wait of a evaluate to true. • Tokens: An edge (u, v) has a token if and only if the ith occurrence of v precedes the ith occurrence of u in any execution, for all i > 1, i ∈ N. • Delay Function: A function that, for each edge (u, v), evaluates to the minimum delay between an occurrence of assignment u and the subsequent occurrence of assignment v. 5 2.3.1 Parallel composition We can use constraint graphs to model collections of repetitive SLHSE without the restrictions that S and T be sequences. For a program fragment . . . a1 ; (w ; a2 ; . . . ), (w 0 ; a20 . . . ); . . . The constraining waits and assignments of a2 are w and a1 . Similarly, the constraining waits of a02 are w0 and a1 . For program fragments . . . ; (. . . ; a1 ; w ), (. . . ; a10 ; w 0 ); a2 . . . The constraining waits of a2 are w and w0 . The constraining assignments are a1 and a01 . The constraining waits of other assignments can be determined in the usual manner. Example 2 Figure 1 shows the constraint graph of the HSE PCHB ≡ init; [true]; lo↑; [ri]; ro↓; [¬li]; lo↓; [true]; *[[¬ri ∧ li]ro↑; [true]; lo↑; [ri]; ro↓; [¬li]; lo↓; [true]] init ≡ lo↓, ro↑; {ri = false ∧ li = true} li↑ ro↑ lo↑ ri↑ li↓ ro↓ lo↓ ri↓ li↑ ro↑ Figure 1: Constraint graph of PCHB 3 Messages A message is distinct from a token in a constraint graph. A ”message” corresponds to a value on a communication channel. We define the number of messages in pipelines and rings and show how the number of messages in rings and pipelines can be changed. If the first non-vacuous action in S that a process π performs on the variables implementing a channel is a wait, then the channel is said to be a passive channel of the process. Otherwise the channel is said to be an active channel of the process. 6 A buffer is a process with exactly two channels, one of which is passive and the other active. A pipeline is a sequence of one or more processes such that for all but the last process in the sequence, exactly one passive channel of a process is an active channel of the next process in the sequence. One active channel of the first process in the sequence is said to be the active channel of the pipeline; one passive channel of the last process in the sequence is said to be the passive channel of the pipeline. For processes that have more than one active channel and/or more than one passive channel, any passive channel such that it is neither the passive channel of the the pipeline nor the active channel of the next process in the sequence is connected to a source/sink. Similarly any active channel of a process that is neither the active channel of the pipeline nor a passive channel of the previous process in the sequence is connected to a source/sink. A ring of buffers is a pipeline such that the active channel of the pipeline is also the passive channel of the pipeline. In the proceeding sections, we will refer to one of the channels as the L channel of a pipeline, and the other channel as the R channel of the pipeline. We will adopt the convention that the L channel of a pipeline is implemented using the variables li and lo; the R channel is implemented using the variables ri and ro. The variables li and ri are only assigned to by the environment; the variables lo and ro are only assigned to by the pipeline being considered. When multiple pipelines are being consider, the variables li, lo, ri, ro will be subscripted with the name of the pipeline that the variables correspond to. In order to determine the number of messages in a pipeline, it will be necessary to keep a count of the number of times certain variables in the system are assigned to. To keep track of the number of times a variable, v, has been assigned to we introduce a ghost variable cv that is initialized to zero. Each assignment v := a in the system is replaced by the pair of assignments hv := a; cv := cv + 1i. We use the notation hSi to indicate that S is an atomic action. In the rest of this thesis, the variables cri and clo are the ghost variables that count the number of assignments to ri and lo, respectively. 3.1 Pipelines 3.1.1 Initial messages Definition 2 The number of initial messages in π, init msg(π), is given by init msg(π) = cri−clo when no more assignments 2 to ri can occur in the system: InitL ; IL ; lo 0 := lo; [lo 6= lo 0 ]; li := ¬li k π k InitR ; cri := 0; IR ; *[ro 0 := ro; [ro 6= ro 0 ]; hri := ¬ri; cri := cri + 1i] where: • InitL initializes the L channel of π. 7 • InitR initializes the R channel. • IR is the assignment hri := ¬ri; cri := cri + 1i if the R channel of π is passive, skip otherwise. • IL is the assignment li := ¬li if the L channel of π is passive, skip otherwise. 3.1.2 Messages during the execution Definition 3 The number of messages in a pipeline, π, in the system InitL ; IL ; *[lo 0 := lo; [lo 6= lo 0 ]; li := ¬li] k π k InitR ; cri := 0; IR ; *[ro 0 := ro; [ro 6= ro 0 ]; hri := ¬ri; cri := cri + 1i] is given by m = clo−cri + init msg(π). 2 Let πA · πB denote the pipeline such that the R channel of pipeline πA is the L channel of πB . Lemma 1 The number of messages in the pipeline π ≡ πA · πB is the sum of the number of messages in πA and πB . LemmaProof 1 Since the R channel of πA is the L channel of πB if the number of messages in πA has been decreased by n, the number of messages in πB must have been increased by n at any point during the execution of π. Since each communication channel is used on every cycle, the number of messages that can be removed from a pipeline is the sum of the number of initial messages in the pipeline and the number of messages inserted into the pipeline. Thus, init msg(π) = init msg(πA ) + init msg(πB ). The number of messages in π is given π by init msg(π) + cloπ −cri . The number of messages in πA is init msg(πA ) + 2 clo −cri messages in πB is init msg(πB ) + πB 2 πB . cloπA −criπA . 2 The number of Since cloπB = criπA , the number of messages in π can be rewritten as init msg(πA ) + init msg(πB ) + cloπ − criπA + cloπB − criπ . 2 Since loπA is another name for loπ and riπB is another name for riπ , the number of messages in π is equal to the sum of the number of messages in πA and πB . 2 3.1.3 Changing the number of messages in a pipeline The number of messages in a pipeline π is increased by n when the program in definition 3 is executed in = n. such a manner that clo−cri 2 8 3.2 Rings Consider a pipeline π such that the initial values of the variables lo and ri are equal, and the values of the variables li and ro are equal. A ring can be formed by merging the variables li and ro into one variable, and merging lo and ri into another variable. The ring thus formed is said to be the ring formed by connecting the R channel of π to its L channel. Recall that either the L channel is active and the R channel is passive or vice versa. Consider a ring r and some channel on r implemented by the variable pair a, b. The channel must be an active channel of some process p1 and the passive channel of some process p2 . Let a be the variable that is assigned to by p1 , and b be the variable assigned to by p2 . In p1 , replace all assignments to a by assignments to the variable a1 ; replace waits on b with waits on b1 . Similarly, in p2 , replace all assignments to b with assignments to b2 and waits on a with waits on a1 . The resulting pipeline is said to be the pipeline formed by disconnecting the ring r at the channel (a, b). The channel (a1 , b1 ) is the active channel of the pipeline, and (a2 , b2 ) the passive channel of the pipeline. 3.2.1 Initial messages The number of initial messages on a ring, r, is the number of initial message in a pipeline formed by disconnecting r at some channel. Lemma 2 All pipelines, π, formed by disconnecting a ring, r, have the same number of initial messages. LemmaProof 2 Consider pipelines π1 and π2 obtained by disconnecting the same ring at two different channels. There exist pipelines πA and πB such that π1 ≡ πA · πB , and π2 ≡ πB · πA . From lemma 1, init msg(π1 ) must be init msg(πA ) + init msg(πB ). Similarly, init msg(π2 ) must be init msg(πB ) + init msg(πA ). 2 Definition 4 For any ring, r, init msg(r) = init msg(πr ) where πr is any pipeline formed by disconnecting r. 3.2.2 Messages during the execution Since a process, p, uses each communication channel exactly once per cycle, the number of messages on a ring is constant. 9 3.2.3 Changing the number of messages on a ring In this section, we describe a method to change the number of messages on a ring. We also discuss how the placement of tokens in the constraint graph of a ring is affected when the number of messages on the ring is changed. The number of messages on a ring can be changed by disconnecting the ring, changing the number of messages in the pipeline formed, and then connecting the active channel of the resulting pipeline to its passive channel to form a ring. Lemma 3 The number of messages on a ring can only be changed by integral amounts. LemmaProof 3 In order to be able to compose πr with itself to form a ring, li and ro must be initialized to the same values. Similarly, lo and ri must be initialized to the same values. In order to be able to connect the passive channel of πr to the active channel of πr to form a ring after inserting/removing messages, li must have the same value as ro and lo must have the same value as ri. Thus either both in and out must be even, or both must be odd. In either case, the number of messages inserted . Since clo − cri is even, the number of messages inserted into the ring must be integral. is given by clo−cri 2 2 Next, we classify all the cycles in a ring. We will use this classification of cycles to study how the number of tokens on a cycle is affected by changing the number of messages on a ring. Given a ring, r, let πr be a pipeline formed by disconnecting the ring r at some channel. The paths in the constraint graph of πr between its input variables and output variables can be grouped into three categories: 1. σ paths—paths from an assignment of li to an assignment of lo and paths from an assignment of ri to an assignment of ro. 2. ρ paths—paths from an assignment of li to an assignment of ro. 3. λ paths—paths from an assignment of ri to an assignment of lo. Figure 2 labels the paths in the constraint graph of πr between assignments to input variables of πr and assignments to output variables of πr . Each label consists of two parts, the first specifies which of the three groups the path belongs to and the second is an index that along with the groups specifies the source and sink of the path. According to this classification, any cycle in the constraint graph of a ring, r, is either a cycle in the 10 ro↑ li↑ lo↑ σ0 σ1 σ2 li↓ lo↓ ri↑ ro↓ σ3 ri↓ ro↑ li↑ li↑ lo↑ li↓ lo↓ li↑ σ4 ro↑ li↑ ri↑ lo↑ σ5 ro↓ σ7 σ6 li↓ ρ0 ρ1 ro↑ li↑ ri↑ lo↑ ro↑ ri↑ λ0 λ1 ρ3 ro↓ li↓ ro↓ λ2 ri↓ ro↑ lo↓ ρ2 li↑ ri↓ lo↓ ro↑ li↑ λ3 ri↓ ro↑ Figure 2: Classification of paths in a pipeline constraint graph of πr , or can be expressed as a composition of paths in πr that matches the regular expression C = F2 |F1 |Loc|B1 |B2 (4) F2 = ρ 1 ρ 2 (5) F1 = ρ0 |ρ1 σ2 σ4 |ρ1 σ3 σ6 |ρ2 σ0 σ5 |ρ2 σ1 σ7 |ρ3 (6) B 2 = λ 1 λ2 (7) B1 = λ0 |λ1 σ6 σ0 |λ1 σ7 σ2 |λ2 σ4 σ1 |λ2 σ5 σ3 |λ3 (8) Loc = σ0 σ4 |σ1 σ6 |σ2 σ5 |σ3 σ7 |σ0 σ5 σ3 σ6 |σ1 σ7 σ2 σ4 |ρ1 σ2 λ1 σ6 |ρ1 σ3 λ2 σ4 |ρ2 σ0 λ1 σ7 |ρ2 σ1 λ2 σ5 (9) Consider a ring r, and pipeline πr formed by disconnecting the ring at some point. If a cycle in the constraint graph of r consists of a path in πr that matches one of the regular expressions (5)–(8), then the cycle will consist of paths matching the same regular expression in any pipeline formed by disconnecting r. Let c(v) denote the number of times assignment v occurs when the number of messages in π r increases by n. After increasing the number of messages in πr by n, the pipeline’s active channel can be connected with its passive channel to form a ring. Thus the sequencing of the handshake implies that after the number of messages in πr has increased by n: c(li ↑) − c(ro ↑) = c(li ↓) − c(ro ↓) = c(lo ↑) − c(ri ↑) = c(lo ↓) − c(ri ↓) = n (10) e = c(li ↑) − c(li ↓) ∈ {−1, 0, 1} (11) a = c(li ↑) − c(lo ↑) ∈ {−1, 0, 1} (12) b = c(li ↑) − c(lo ↓) ∈ {−1, 0, 1} (13) 11 li ↑ li ↓ ri ↑ ri ↓ lo ↑ a a−e −n a−b−n lo ↓ b b−e b−a−n −n ro ↑ n n−e −a −b ro ↓ n+e n −a + e −b + e Table 1: Change in number of tokens on path when the number of messages is increased by n Table 1 shows the change in the number of tokens on the various classes of paths the number of messages in πr has increased by n. The table is easily derived from (10)–(13). Lemma 4 Changing the number of messages in a ring by n ∈ Z changes the number of tokens on any cycle in a ring’s constraint graph by an amount independent of the channel at which the ring was disconnected to insert the messages. LemmaProof 4 Changing the number of messages on a ring, by an integral amount only changes the number of messages on cycles matching F1 , F2 , B2 , B1 . If a cycle matches one of F1 , F2 , B2 , B1 when a ring is disconnected at a particular channel, it must match the same expression, no matter where the ring is disconnected. Inspection of table 1 and (4) reveals that inserting a message into a ring, changes the number of tokens on all cycles matching one of the expressions F1 , F2 , B2 , B1 , by the same amount. 2 4 Static slack In this section the static slack of a buffer is defined. For processes with multiple passive channels and/or active channels, the static slack of the process between a specified pair of passive and active channels is defined as for a buffer, with all other channels being connected to sources and sinks. 4.1 Pipelines Static slack measures the maximum number of messages a buffer, or pipeline of buffers can contain. Definition 5 Static Slack: Pipeline The static slack of a pipeline π, is s = (clo − cri) /2 + init msg(π) when no more assignments can be performed on li in the following program: InitL ; IL ; *[lo 0 := lo; [lo 6= lo 0 ]; li := ¬li] k π k InitR ; IR ; ro 0 := ro; [ro 6= ro 0 ]; hri := ¬ri ; cri := 1i 12 4.2 Rings Definition 6 Static Slack: Ring The static slack of a ring of buffers is the maximum number of messages that can be on the ring. Consider a pipeline, π, of process such that its passive channel can be connect to its active channel to form a ring. If a ring of n instances of π has static slack sn , then π must have static slack snn . Since the static slack need not be integral, the static slack must be measured by considering a sequence of rings composed of π. Definition 7 Static Slack : Pipeline when part of a ring The static slack, s, of a pipeline, π, when part of a ring can be measured as s = lim n→∞ sn , n where sn is the static slack of a ring of n instances of π. The definition of static slack of a ring is a special case of the definition of the dynamic slack of a ring. The proof that this limit exists will follow from the proof that the corresponding limit in the definition of the dynamic slack exists. 5 Dynamic slack and Dynamic Threshold The cycle time of a ring of buffers varies with the number of messages on the ring. Inserting a message into the ring adds tokens to some cycles and removes tokens from others. This imposes a two sided constraint on the number of messages needed for a ring to maintain a specified cycle time, τ . The upper bound will be referred to as the dynamic slack of the ring at τ , and the lower bound as the dynamic threshold at τ . In the interest of clarity, the dynamic slack and dynamic threshold are defined for a pipeline of buffers. For pipelines of processes with multiple passive channels and/or multiple active channels, dynamic slack and dynamic threshold between the L and R channels of the pipeline are defined as for a pipeline of buffers, with all other channels being connected to infinitely fast sources or sinks. 5.1 Dynamic Slack We will define the dynamic slack of a ring, the dynamic slack of a pipeline, when part of a ring and the dynamic slack of a pipeline when part of a larger pipeline. We will show that the dynamic slack of a pipeline when part of a ring equals the dynamic slack of a pipeline when part of a larger pipeline. 13 5.1.1 Ring Definition 8 Dynamic Slack: Ring The dynamic slack ds(r, τ ), of a ring of buffers, r, at cycle time, τ , is defined as the maximum number of messages that r can contain such that its cycle time is no greater than τ . The dynamic slack of a pipeline, π, when part of a ring is defined only for pipelines that are initialized in such a manner that their passive and active channels can be connected to form a ring. If a ring, r n , composed of n instances of π has dynamic slack ds(rn , τ ), then π is said to have dynamic slack at least ds(rnn ,τ ) . The ratio of the dynamic slack of a ring to the number of processes on the ring need not be constant. Therefore, the dynamic slack is measured by considering a sequence of rings composes of n instances of π. A ring composed of n instances of π may not be able to operate at the cycle time τ , for all n ∈ N. We consider rings composed of L(i) instances of π where L(i) is the ith smallest n ∈ N such that a ring of n instances of π can operate at cycle time τ . Definition 9 Dynamic Slack: Pipeline when part of a ring The dynamic slack, dsring (π, τ ), of a pipeline, π, when part of a ring is defined as def dsring (π, τ ) = lim i→∞ ds(rL(i) , τ ) , L(i) where rL(i) is a ring of L(i) instances of π. Note that dsring (π, ∞) is the static slack of the pipeline when part of a ring. We proceed to show that this limit exists. We first prove a lemma that relates the dynamic slack of a ring composed of n instances of a pipeline and the dynamic slack of rings composed i · n, i ∈ N instances of the pipeline. This lemma is used to prove that the limit exists. Lemma 5 Let rn be a ring of n instances of a pipeline, π that has cycle time at most τ . There exists κn ∈ R such that ds(rn , τ ) = init msg(rn ) + bκn c and ds(ri·n , τ ) = i · init msg(rn ) + bi · κn c for all i ∈ N where ri·n is a ring of i · n instances of π. LemmaProof 5 Consider any simple cycle, j, in the constraint graph of rn . Let ∆j be the delay along this cycle, kj the number of tokens initially present on the cycle, and αj the change in number of tokens on this cycle when a message is added to the ring. 14 Since the ring can operate at the target cycle time, all cycles in the constraint graph of r n must satisfy (3) when there are initially ds(rn , τ ) messages on the ring. Thus, all cycles, j, satisfy (14)–(16) where m = ds(rn , τ ) − init msg(rn ). kj τ − ∆ j ≥−m αj τ if αj > 0. (14) kj τ − ∆j ≥0 if αj = 0. (15) kj τ − ∆ j ≤−m αj τ if αj < 0. (16) Let C(rn ) be the set of cycles in the constraint graph of rn . The dynamic slack of rn is given by  ∆c − k c τ , ds(rn , τ ) = init msg(rn ) + αc · τ  (17) where c is a cycle in the constraint graph of rn such that ∆c − k c τ ∆j − k j τ = min . αc · τ αj · τ j∈C(rn ) We now express the dynamic slack of the ring ri·n in a similar manner. Observe that ri·n has i initial messages for each initial message in ring rn . Thus, ds(ri·n , τ ) is given by  ∆c 0 − k c 0 τ α c0 · τ   ∆c 0 − k c 0 τ , = i · init msg(rn ) + α c0 · τ ds(ri·n , τ ) = init msg(ri·n ) +  (18) (19) where c0 is a cycle such that ∆c 0 − k c 0 τ ∆j − k j τ = min . α c0 · τ αj · τ j∈C(ri·n ) Any cycle in the constraint graph of ri·n can be written as a composition of cycles in rn . For each cycle j in rn , let vj be a non-negative integer that denotes the number of times that cycle j appears when the c 0 is expressed as a composition of cycles in rn . ∆c 0 = X v j · ∆j (20) X vj · kj (21) X v j · αj (22) j k c0 = j i · α c0 = j The cycle c0 must have α < 0. Furthermore, from the arguments in section 2.1.1, only simple cycles need 15 to be considered. Table 1 and (4) show that simple cycles have |α| ≤ 2. If αc0 = −1, then the cycle c† that traverses each edge in cycle c0 twice has αc† = −2 and ∆c 0 − k c 0 τ ∆ † − k c† τ = c . α c0 · τ α c† · τ Thus we can restrict our attention to the case where αc0 = −2. From (20)–(22), and the definition of c0 , we have that ∆c 0 − k c 0 τ = P min α c0 · τ vj ·αj =−2i i P j vj (∆j − kj τ ) P τ v j · αj (23) j j i P vj (kj τ − ∆j ) P . −τ vj · αj j = P min vj ·αj =−2i (24) j j Note that i, τ and vj are non-negative. From (15) we note that when (24) is minimized vj = 0 ∀j : αj = 0. Thus, P j:αj 6=0 ∆c 0 − k c 0 τ = P min α c0 · τ vj ·αj =−2i v j αj  kj τ −∆j αj 2τ  . (25) j (25) is minimized when vj = 0 ∀j 6= c, vc = |α2ic | . Therefore,   2i (∆c − kc τ ) ds(ri·n , τ ) = i · init msg(rn ) + −2 |αc | · τ   i (∆c − kc τ ) = i · init msg(rn ) + . αc · τ (26) (27) cτ This proves the lemma for κn = ∆cα−k 2 c ·τ Theorem 1 Consider a pipeline π for which a ring of h instances of π operate at cycle time at most τ . There exists κh ∈ R such that if ds(rh , τ ) = init msg(rh ) + bκh c, dsring (π, τ ) = init msg(π) + κhh . Proof 1 We use the notation rn to denote a ring consisting of n instances of a pipeline π. Recall that def ds(rL(i) , τ ) i→∞ L(i) dsring (π, τ ) = lim 16 In order to prove the theorem, we need to show that for any  > 0, there exists I such that for all i ≥ I, ds(rL(i) , τ ) κh ≤ − init msg(π) + L(i) h In order to prove this, we bound the difference between ds(rn , τ ) and (init msg(π) + κhh ). For n ∈ [j · h, (j + 1) · h], from lemma 5 ds(rj·n·h , τ ) ≤ j · h · (ds(rn , τ ) + 1) (28) Using lemma 5, substitute for the left hand side of the inequality j · n · init msg(rh ) + bj · n · κh c ≤ j · h · (ds(rn , τ ) + 1) (29) n (j · init msg(rh ) + bj · κh c) ≤ j · h · (ds(rn , τ ) + 1) (30) Rewriting j · init msg(rh ) + bj · κh c ≤ ds(rn , τ ) + 1 (31) (j + 1) · h · ds(rn , τ ) ≤ ds(r(j+1)·n·h , τ ) (32) From lemma 5, Applying the lemma to the right hand side and rewriting, (j + 1) · h · ds(rn , τ ) ≤ (j + 1) · n · init msg(rh ) + (j + 1) · n · κh ≤ n ((j + 1) · init msg(rh ) + (j + 1) · κh ) ds(rn , τ ) ≤ (j + 1) · init msg(rh ) + (j + 1) · κh (33) (34) (35) Recall that init msg(rh ) = h · init msg(π). Let X = init msg(rh ). Thus,   ds(rn , τ ) X + κh j · (X + κh ) − 2 X + κh (j + 1) · (X + κh ) X + κh − ∈ − , − n h (j + 1) · h h j ·h h   − init msg(rh ) − κh − 2 init msg(rh ) + κh , ∈ (j + 1) · h j·h (36) (37) Thus, for L(i) ∈ [j · h, (j + 1) · h], ds(rL(i) , τ ) init msg(rh ) + κh 2 + init msg(rh ) + κh ≤ − L(i) h j ·h 17 (38) h )+κh + h, (39) holds. Recall that L(i) is increasing in i. Thus, for all i > I such that L(I) > 2+init msg(r  ds(rL(i) , τ ) init msg(rh ) + κh − ≤ L(i) h (39) This proves the theorem. 2 5.1.2 Pipelines In this section we study the dynamic slack of a pipeline, π. The dynamic slack is the maximum number of messages an instance of π can contain whilst maintaining a cycle time of τ . Definition 10 Dynamic Slack: Pipeline Consider a sequence of pipelines, {πn }, such that πn is the pipeline consisting of n instances of π. The dynamic slack of π is def dspip (π, τ ) = lim n→∞ mn , n where mn is the maximum number of messages in πn during the steady state of any fastest linear execution of the system L k πn k R where L and R are sources/sinks that have delay 0 between their input and output variables. It is required that there be a delay of τ between two successive actions on communication variables assigned to by R. In this section, when we refer to an execution of a pipeline, if the environment of the pipeline is unspecified, the environment of the pipeline is assumed to be that described in definition 10. We will prove a lemma that relates the dynamic slack of a ring of buffers to the maximum number of messages in the steady state of a fastest linear execution of a pipeline obtained by disconnecting the ring. This lemma will be used to prove that the limit in definition 10 exists, and is equal to the dynamic slack of the pipeline when part of a ring. Lemma 6 Consider a ring rn , that consists of n instances of a pipeline, π. If rn can operate at cycle time τ or lower, then any fastest linear execution of π2n contains no more than ds(r2n , τ ) + 1 messages in the steady state. LemmaProof 6 Using the notation from section 3.2.3, the cycle in the constraint graph of the ring r 2n that limits the maximum number of messages on the ring is a cycle that is either a λ0 or λ3 path in π2n . Label this path p. Since r2n has cycle time at most τ , the ratio of the delay along the cycle to the number of tokens on the cycle is less then τ . 18 Consider a pipeline π2n , and its fastest linear execution. In the stead state, the number of tokens on p varies by at most one. The path p needs to have at least δ(p) τ tokens at during the steady state of a fastest linear execution of π2n , where δ(p) is the delay along p. Thus, during a fastest linear execution π2n must have at least δ(p) τ − 1 tokens on p in the steady state. This corresponds to there being at most ds(r 2n , τ ) + 1 messages in π2n . 2 Theorem 2 If there exists h such that a ring composed of h instances of π has an execution with cycle time at most τ , then dspip (π, τ ) = dsring (π, τ ). Proof 2 The proof of this theorem is structured in the same fashion as that of theorem 1. We will bound the difference between mn and dsring (π, τ ) for all n > h. Given a linear execution of ring r2j·h with ds(r2j·h , τ ) messages such that the cycle period of any vertex is exactly τ , an execution of pipeline πn : n ≥ 2j · h can be constructed by setting the state of k 0 th process on the pipeline to be the state of the process (k mod 2j · h)th on the ring. During this execution there are at least ds(r2j·h , τ ) messages in πn . From theorem 1, 2j · h · dsring (π, τ ) − 1 ≤ ds(r2j·h , τ ) ≤ 2j · h · dsring (π, τ ) Thus mn ≥ 2j · h · dsring (π, τ ) − 1 (40) For all pipelines πn such that n ≤ 2 (j + 1) · h. mn must satisfy (41). Applying lemma 6, we obtain (42). mn < m2(j+1)·h (41) < 2 (j + 1) · h · dsring (π, τ ) + 1 (42) Thus, for any pipeline πn such that n ∈ [2j · h, 2 (j + 1) h],   2j · h · dsring (π, τ ) − 1 2 (j + 1) · h · dsring (π, τ ) + 1 mn − dsring (π, τ ) ∈ − dsring (π, τ ), − dsring (π, τ ) n 2(j + 1)h 2j · h (43) ∈   −2h · dsring (π, τ ) − 1 2h · dsring (π, τ ) + 1 , , , and 2(j + 1)h 2j · h 1 dsring (π, τ ) + 2h mn − dsring (π, τ ) ≤ . n j (44) (45) 19 Note that for any  > 0, there exists N = 1 dsring (π,τ )+ 2h  such that for all n > 2(N + 1)h, mn − dsring (π, τ ) < . n (46) Thus, def dspip (π, τ ) = lim n→∞ mn = dsring (π, τ ). n (47) 2 5.2 Dynamic Threshold We will define the dynamic threshold of a ring, the dynamic threshold of a pipeline, when part of a ring and the dynamic threshold of a pipeline when part of a larger pipeline. We will show that the dynamic threshold of a pipeline when part of a ring equals the dynamic threshold of a pipeline when part of a larger pipeline. The definitions presented in this section are very similar to the definitions of dynamic slack presented in section 5.1. Like dynamic slack, dynamic threshold is defined as a limit. The proofs that these limits exist closely mirrors the corresponding proofs for dynamic slack. In this section we will simply state the theorems. The proofs of these theorems are provided in appendix A. 5.2.1 Ring Definition 11 Dynamic Threshold: Ring The dynamic threshold dt(r, τ ), of a ring of buffers, r, at cycle time,τ , is defined as the minimum number of messages that r must contain such that its cycle time is no greater than τ . Next we define the dynamic threshold of a pipeline, π when part of a ring. The dynamic threshold of a pipeline, when part of a ring is only defined when the input and output channels of the pipeline are initialized in such a manner that the input channel can be be connected to the output channel to form a ring. If a ring, rn , composed of n instances of π has dynamic threshold dt(rn , τ ), then π must have dynamic threshold dt(rnn ,τ ) . The dynamic threshold need not be rational, therefore, the dynamic threshold is measured by considering a sequence of rings composed of n instances of π. A ring composed of n instances of π may not be able to operate at the target cycle time for all n ∈ N. Thus, we consider rings composed of L(i) instances of π where L(i) is the ith smallest n ∈ N such that a ring of n instances of π can operate at the target cycle time. 20 Definition 12 Dynamic Threshold: Pipeline when part of a ring The dynamic threshold, dtring (π, τ ), of a pipeline, π, when part of a ring is defined as def dtring (π, τ ) = lim i→∞ dt(rL(i) , τ ) L(i) where rL(i) is a ring of L(i) instances of π. We now proceed to show that this limit exists. This proof is very similar to the corresponding proof for dynamic slack. We first state a lemma that relates the dynamic threshold of a ring composed of n instances of π to that of a ring composed of i · n, i ∈ N instances of π. This lemma can be used to prove that the limit exists. Lemma 7 Let rn be a ring of n instances of a pipeline, π that has cycle time at most τ . There exists κn ∈ R such that dt(rn , τ ) = init msg(rn ) + dκn e and dt(ri·n , τ ) = i · init msg(rn ) + di · κn e for all i ∈ N where ri·n is a ring of i · n instances of π. Theorem 3 Consider a pipeline π for which there exists h such that a ring of h instances of π has cycle time at most τ . There exists κh ∈ R such that if dt(rhh ,τ ) = init msg(rh ) + dκh e, dtring (π, τ ) = init msg(π) + κhh . 5.2.2 Pipelines In this section we study the dynamic threshold of a pipeline, π. The dynamic threshold is the minimum number of messages an instance of π, can contain, whilst maintaining a cycle time of τ . Definition 13 Dynamic Threshold: Pipeline Consider a sequence of pipelines, {πn }, such that πn is the pipeline consisting of n instances of π. Let each instance of π contain the minimum number of messages such that π can be composed with itself. The dynamic threshold of π is def dtpip (π, τ ) = lim n→∞ mn n where mn is the minimum number of messages in πn in the steady state of any fastest linear execution of the system: L k πn k R 21 where L is source that has delay 0 between its input and output variables. However, there is a delay of τ between two successive actions on communication variables assigned by L. R is an infinitely fast sink. In this section, when we refer to the execution of a pipeline, if the environment of the pipeline is unspecified, the environment of the pipeline is assumed to be that described in definition 13. We will state a lemma that relates the dynamic threshold of a ring of buffers to the minimum number of messages in the steady state of a pipeline obtained by disconnecting the ring. This lemma can be used to prove that the limit in definition 13 exists, and is equal to the dynamic threshold of the pipeline when part of a ring. Since the proofs are very similar to the corresponding proofs for the dynamic slack, we list the proofs in appendix A Lemma 8 Consider a ring rn , that consists of n instances of a pipeline, π. Let πn be the pipeline that consists of n instances of π. If rn can operate at cycle time τ or lower, then in any fastest linear execution of π 2n , π2n contains no less than dt(r2n , τ ) − 1 messages. Theorem 4 If there exists h such that a ring composed of h instances of π has an execution with cycle time at most τ , then dtpip (π, τ ) = dtring (π, τ ). 6 Dynamic Slack and Dynamic Threshold of Half-Buffers Lines [4] presents all the possible reshufflings of an ∗[L; R] buffer that do not require data to be stored on state variables within the buffer. Of these reshufflings, PCHB, WCHB, B1,B4, and B5 have static slack 1 2 . Sufficient conditions are presented under which the dynamic slack (and dynamic threshold) of a pipeline composed of processes with any of the first four reshufflings is the sum of that of the processes in the pipeline. 6.1 Buffers First, systems composed of buffers are considered. We will define bounds on the delays of the various paths between the input and output variables of a buffer. We will further need to make some assumptions about the delays of adjacent buffers in a pipeline. This, along with assumptions on the intersections of paths, will be used to identify the cycles that limit the minimum and maximum number of messages that a pipeline can contain at a specified cycle time τ . All the paths between input and output variables of a process are classified as in section 3.2.3. We will use the notation λ0 (p0 ) to denote a λ0 path of the process p0 . 22 Path λ0 λ1 λ2 λ3 ρ0 ρ1 ρ2 ρ3 Delay ≤ bi + τ2 = bi = bi ≤ bi + τ2 = fi ≤ fi + τ2 ≤ fi + τ2 ≤ fi + ki τ Tokens 1 0 1 1 0 1 0 ki Path σ0 σ1 σ2 σ3 σ4 σ5 σ6 σ7 Delay = xi ≤ ui + τ2 ≤ vi + τ2 = ri ≤ wi + τ2 = yi = si ≤ zi + τ2 Tokens 1 1 1 0 0 0 0 1 Table 2: Bounds on delays in process pi j ∈ {i} j ∈ {i, i + 1} j ∈ {i, i + 1} j ∈ {i, i + 1, i + 2} fi + bj ≤ τ2 wi + xj ≤ τ2 wi + vj ≤ τ2 si + uj ≤ τ2 wi + uj ≤ τ2 si + rj ≤ τ2 si + xj ≤ τ2 zi + vj ≤ τ2 yi + xj ≤ τ2 yi + vj ≤ τ2 zi + rj ≤ τ2 zi + uj ≤ τ2 yi + rj ≤ τ2 Table 3: Constraints on delays of connected processes In order to simplify the set of possible cycles in a constraint graph, we need to make assumption 1. Note that the constraint graph of a half buffer with reshuffling B5 does not satisfy the assumption. However, half buffers implementing one of the other four reshufflings do satisfy the assumption. Assumption 1 For any process, p 1. all ρ1 and ρ2 paths intersect all λi paths 2. all ρ0 paths intersect all λi paths such that i 6= 1 3. all ρ3 paths intersect all λi paths such that i 6= 2 4. all ρ0 paths intersect all σ2 paths 5. all ρ3 paths intersect all σ1 paths Table 2 defines bounds on the delays between input and output variables of a process p i , and lists the number of tokens on such paths when there are no messages in the process. The bounds on the delays along the paths depend on the specified time, τ . Assumption 2 The delay on the paths between input and output variables of a process must satisfy the constraints in table 2. Furthermore, the constraints in table 3 must be satisfied for all processes. We will consider systems composed of processes that have one of the four remaining reshufflings 23 PCHB ≡ [true]; lo↑; [ri]; ro↓; [¬li]; lo↓; [true]; *[[¬ri ∧ li]ro↑; [true]; lo↑; [ri]; ro↓; [¬li]; lo↓; [true]] WCHB ≡ [true]; lo↑; [ri ∧ ¬li]; ro↓; [true]; lo↓; [true]; *[[¬ri ∧ li]; ro↑; [true]; lo↑; [ri ∧ ¬li]; ro↓; [true]; lo↓; [true]] B 1 ≡ [true]; lo↑; [ri ∧ ¬li]; lo↓; [true]; ro↓; [true]; *[[¬ri ∧ li]; ro↑; [true]; lo↑; [ri ∧ ¬li]; lo↓; ro↓; [true]] B 4 ≡ [true]; lo↑; ([ri]; ro↓), ([ri ∧ ¬li]; lo↓); [true]; *[[¬ri ∧ li]; ro↑; [true]; lo↑; ([ri]; ro↓), ([ri ∧ ¬li]; lo↓); [true]] All process are initialized with the program: init ≡ lo↓, ro↑, [¬ri ∧ li] Figure 3 shows the constraint graphs for such buffers. PCHB WCHB li↑ ro↑ li↑ ro↑ lo↑ ri↑ lo↑ ri↑ li↓ ro↓ li↓ ro↓ lo↓ ri↓ lo↓ ri↓ li↑ ro↑ li↑ ro↑ B4 B1 li↑ ro↑ li↑ ro↑ lo↑ ri↑ lo↑ ri↑ li↓ ro↓ li↓ ro↓ lo↓ ri↓ lo↓ ri↓ li↑ ro↑ li↑ ro↑ Figure 3: Constraint graphs of half buffers In addition to assumptions 1 and 2, it is assumed that the ratio of the delay to the number of tokens on cycles that traverse exactly one process is at most τ . If this were not the case, the dynamic slack and dynamic threshold for any system composed of such processes would be undefined. Adding buffers to the system does not change the number of tokens on such cycles. The L channel of a buffer is referred to as its input channel, and the R channel its output channel. We will refer to cycles in a pipeline of processes matching regular expression (9) as local cycles. 24 Lemma 9 If assumptions 1 and 2 hold, all simple local cycles traverse no more than 3 processes. Furthermore, no simple local cycle constrains the cycle time to be greater than τ . LemmaProof 9 Consider a local cycle traversing greater than 3 processes. There must be at least one process, p 0 , such that the cycle traverses no λi (p0 ) : i ∈ {0, 1, 2, 3} and no ρi (p0 ) : i ∈ {0, 1, 2, 3} paths, but traverse at least one σj (p0 ) : j ∈ {4, 5, 6, 7} path. Let p1 and p2 be the processes such that the input channel of p2 is the output channel of p1 and the input channel of p1 is the output channel of p0 . If the local cycle traverse greater than 3 processes, it must traverse p 0 , p1 and p2 . Furthermore, the cycle must contain at least one λi and ρi edge from both p1 and p2 . The only pairs of paths, ρi (p), λj (p) : i, j ∈ {0, 1, 2, 3}, such that the paths do not intersect are ρ0 (p), λ1 (p) and ρ3 (p), λ2 (p). Thus the local cycle must have one of the following sets of paths 1. ρ0 (p1 ), ρ0 (p2 ), λ1 (p2 ), σ7 (p1 ), σ2 (p2 ), λ1 (p1 ) 2. ρ0 (p1 ), ρ3 (p2 ), λ2 (p2 ), σ7 (p1 ), σ1 (p2 ), λ1 (p1 ) 3. ρ3 (p1 ), σ2 (p2 ), σ4 (p1 ), ρ0 (p2 ), λ1 (p2 ), λ2 (p1 ) 4. ρ3 (p1 ), σ1 (p2 ), σ4 (p1 ), ρ3 (p2 ), λ2 (p2 ), λ2 (p1 ) All four sets contain paths that intersect, hence the cycle cannot be simple. If a simple local cycle traverses three processes p0 , p1 and p2 ,the cycle can contain only on λi (p1 ) and one ρj (p1 ) path, where i, j ∈ {0, 1, 2, 3}. Table 4 lists all simple cycles traversing 2 processes. Table 5 lists all simple cycles traversing 3 processes. Table 3 shows that these processes cannot constrain the cycle time to be greater than τ . Changing the number of messages on a ring does not change the number of tokens on local cycles, thus these cycles can never constrain a ring’s cycle time to be greater than τ . 2 A cycle that matches one of the regular expressions (5)–(8) is referred as a global cycle. A simple global cycle can traverse a ring at most twice. Thus, we need only consider simple global cycles in even length rings that traverse a ring once. Global cycles matching one of the regular expressions (5) or (6) are referred to as forward cycles. Global cycles matching one of the regular expressions (7) or (8) are referred to as backward cycles. A critical cycle of a system is a cycle such that ratio of the delay along the cycle to the number of tokens on the cycle equals the system’s cycle time. 25 Edges σ0 (p1 )σ4 (p0 ) σ1 (p1 )σ6 (p0 ) σ2 (p1 )σ5 (p0 ) σ3 (p1 )σ7 (p0 ) σ0 (p1 )σ5 (p0 )σ3 (p1 )σ6 (p0 ) σ1 (p1 )σ4 (p0 )σ2 (p1 )σ7 (p0 ) Delay ≤ x1 + w0 + τ2 ≤ u1 + s0 + τ2 ≤ v1 + y0 + τ2 ≤ r1 + z0 + τ2 = x1 + y0 + r1 + s0 ≤ u1 + v1 + w0 + z0 + 2τ Tokens 1 1 1 1 1 3 Table 4: Local cycles traversing at most 2 processes Edges ρ0 (p1 )σ0 (p2 )λ1 (p1 )σ6 (p0 ) ρ0 (p1 )σ1 (p2 )σ7 (p1 )σ2 (p2 )λ1 (p1 )σ6 (p0 ) ρ3 (p1 )σ3 (p2 )λ2 (p1 )σ5 (p0 ) ρ3 (p1 )σ2 (p2 )σ4 (p1 )σ1 (p2 )λ2 (p1 )σ5 (p0 ) Delay ≤ f 1 + x2 + b 1 + s 0 ≤ f1 + u2 + z1 + v2 + b1 + s0 + 3τ 2 ≤ f 1 + r2 + b1 + y0 + k1 τ ≤ f1 + v2 + w1 + u2 + b1 + y0 + k1 τ + 3τ 2 Tokens 1 3 1 + k1 3 + k1 Table 5: Local cycles traversing 3 processes Lemma 10 If a forward cycle constrains the cycle time of a ring of buffers satisfying assumptions 1 and 2 to be greater than τ , the forward cycle ρ∗0 is a critical cycle. LemmaProof 10 A forward cycle contains a ρi path of each process on the ring. If the cycle contains more than one ρi path, it must also contain a λi edge. However, any cycle containing two ρi (p) paths and a λi (p) path will contain at least 1 pair of intersecting paths thus the cycle cannot be simple. Thus we need to only consider forward cycles with no λi paths. Consider all possible paths from the li ↑ input of process pi to the ro ↑ output of process pi . Since a simple forward cycle cannot traverse any λj (p) edges, any such paths falls in one of three categories, where pi−1 is the process connected to the input channel of pi . 1. ρ0 (pi ) 2. σ0 (pi )σ5 (pi−1 )ρ0 (pi ) 3. σ1 (pi )σ7 (pi−1 )ρ0 (pi ) Using the bounds from table 2, we see that if the cycle that constrains the cycle time of a ring of buffers to be τ has paths of the type 2 and 3, a cycle containing no paths of these two types also determines the cycle time of the systems. Table 6 is used to perform similar analysis to show that forward cycles containing any σ i : i ∈ {0, 1, . . . , 7} edges impose no tighter a constraint on the cycle time than a path that consists of only ρ i edges. 26 li ↑ −ro ↑ path ρ0 (pi ) σ0 (pi )σ5 (pi−1 )ρ2 (pi ) σ1 (pi )σ7 (pi−1 )ρ2 (pi ) li ↓ −ro ↑ path ρ2 (pi ) σ2 (pi )σ4 (pi−1 )ρ0 (pi ) σ3 (pi )σ6 (pi−1 )ρ0 (pi ) Delay = fi ≤ fi + τ ≤ fi + 2τ delay ≤ fi + τ2 ≤ fi + 3τ 2 ≤ fi + τ2 tokens 0 1 2 tokens 0 1 0 li ↑ −ro ↓ path ρ1 (pi ) σ0 (pi )σ5 (pi−1 )ρ3 (pi ) σ1 (pi )σ7 (pi−1 )ρ3 (pi ) li ↓ −ro ↓ path ρ3 (pi ) σ2 (pi )σ4 (pi−1 )ρ1 (pi ) σ3 (pi )σ6 (pi−1 )ρ1 (pi ) Delay ≤ fi + τ2 ≤ fi + ki τ + τ2 ≤ fi + (ki + 1) τ + τ2 delay ≤ fi + ki τ ≤ fi + 2τ ≤ fi + τ tokens 1 1 + ki 2 + ki tokens ki 2 1 Table 6: Possible forward paths across 1 process, pi ρ0 (pi · pi+1 ) paths ρ0 (pi )ρ0 (pi+1 ) ρ1 (pi )ρ2 (pi+1 ) ρ2 (pi · pi+1 ) paths ρ2 (pi )ρ0 (pi+1 ) ρ3 (pi )ρ2 (pi+1 ) delay = fi + fi+1 ≤ fi + fi+1 + τ delay ≤ fi + fi+1 + τ2 ≤ fi + fi+1 + (2ki2+1)τ tokens 0 1 tokens 0 k1 ρ1 (pi · pi+1 ) paths ρ0 (pi )ρ1 (pi+1 ) ρ1 (pi )ρ3 (pi+1 ) ρ3 (pi · pi+1 ) paths ρ2 (pi )ρ1 (pi+1 ) ρ3 (pi )ρ3 (pi+1 ) delay ≤ fi + fi+1 + τ2 ≤ fi + fi+1 + (2ki+12 +1)τ delay ≤ fi + fi+1 + τ ≤ fi + fi+1 + (ki + ki+1 ) τ tokens 1 1+ ki+1 tokens 1 ki + ki+1 Table 7: Possible critical ρi paths in pipeline of 2 processes, pi and pi+1 . Base case: Consider a pair of connected buffers pi and pi+1 , where the output channel of pi is connected to the input channel of pi+1 . Denote this pipeline of processes pi · pi+1 . Let ρi (pi · pi+1 ) denote the class ρi paths in this pipeline. Table 7 lists the paths ρi paths in a pipeline pi · pi+1 . The table shows the number of tokens on the paths when there are no messages in the ring. Note that if the number of tokens on a particular ρ i (pi · pi+1 ) path changes, it must change on all such paths since the paths share the same start and end points. Inspection of table 7, shows that the claimed path is indeed critical in rings of 2 and 4 buffers. Inductive Step: Assume that for all integers n > 1, the claim holds for rings of length at most 2n. Consider a ring of length 2n + 2. This ring can be expressed as a composition of two pipelines π A and πB , of even length such that the critical forward cycle of the ring can be expressed as a composition of a ρ 0 (πA ) and a ρ0 (πB ) path or that of a ρ3 (πA ) and ρ3 (πB ) path. P P P Note that the maximum delay on a ρ3 (π) path is fi + τ ki . This path has ki tokens on it initially. P There is a composition of ρ0 (πA ) and a ρ0 (πB ) path that has delay exactly fi , with 0 tokens initially. Both cycle have the number of tokens changed by the same amount when a message is added to the ring. Thus the ρ3 (πA · πB ) path is no more critical than the ρ0 (πA · πB ) cycle. By assumption, the critical ρ0 (πA ) and ρ0 (πB ) paths must be ρ∗0 . 2 Lemma 11 If a backward cycle constrains the cycle time of a ring to be greater than τ , then (λ 1 λ2 )∗ is a critical backward cycle. 27 ri ↑ −lo ↑ paths λ0 (pi ) σ4 (pi )σ1 λ2 (pi ) σ5 (pi )σ3 λ2 (pi ) ri ↓ −lo ↑ paths λ2 (pi ) σ6 (pi )σ0 (pi+1 )λ0 (pi ) σ7 (pi )σ2 (pi+1 )λ0 (pi ) delay ≤ bi + τ2 ≤ bi + 3τ 2 ≤ bi + τ2 delay = bi + τ2 ≤ bi + τ ≤ bi + 2τ tokens 1 2 1 tokens 1 2 3 ri ↑ −lo ↓ paths λ1 (pi ) σ4 (pi )σ1 λ3 (pi ) σ5 (pi )σ3 λ3 (pi ) ri ↓ −lo ↓ paths λ3 (pi ) σ6 (pi )σ0 (pi+1 )λ1 (pi ) σ7 (pi )σ2 (pi+1 )λ1 (pi ) delay = bi ≤ bi + 2τ ≤ bi + τ delay ≤ bi + τ2 ≤ bi + τ2 ≤ bi + 3τ 2 tokens 0 2 1 tokens 1 1 2 Table 8: Possible backward paths across process pi λ0 (pi · pi+1 ) paths λ0 (pi+1 )λ0 (pi ) λ1 (pi+1 )λ2 (pi ) λ2 (pi · pi+1 ) paths λ2 (pi+1 )λ0 (pi ) λ3 (pi+1 )λ2 (pi ) delay ≤ bi + bi+1 + τ = bi + bi+1 delay ≤ bi + bi+1 + τ2 ≤ bi + bi+1 + τ2 tokens 2 1 tokens 2 2 λ1 (pi · pi+1 ) paths λ0 (pi+1 )λ1 (pi ) λ1 (pi+1 )λ3 (pi ) λ3 (pi · pi+1 ) paths λ2 (pi+1 )λ1 (pi ) λ3 (pi+1 )λ3 (pi ) delay ≤ bi + bi+1 + τ2 ≤ bi + bi+1 + τ2 delay = bi + bi+1 ≤ bi + bi+1 + τ tokens 1 1 tokens 1 2 Table 9: Possible critical λ∗ paths in pipeline of 2 processes pi and pi+1 LemmaProof 11 Any simple backward cycle must contain at least one λi path of each process on the ring. If a backward cycle contains a ρi path of a process, it must contain 2 λi paths of that process. However, for any process a set of 2 λi (p) paths and 1 ρi (p) path, will contain at least one pair of intersecting paths, thus such a cycle would not be simple. Table 8 shows that for any backward path containing σi (p) edges imposes no tighter a constraint on the cycle time than a path consisting solely of λi edges. Table 8 is derived from table 2. Base case: Table 9 lists all the paths from input variables of the output channel to a output variables of input channels in a pipeline of two buffers. The table shows the number of tokens on these paths when no messages are present on the buffers. Note that if the number of tokens on a particular λ i path changes, then the number of tokens on all λi paths must change. Inspection of the table reveals that the claim does indeed hold for rings of length 2 and 4. Inductive step: Assume that for all integers n > 1, the claim holds for rings of length at most 2n. Consider the critical backward cycle of ring of length 2n + 2. The ring of length 2n + 2 can be expressed as a composition of 2 pipelines, πA and πB of even length with the property that the critical cycle consists of either a λ0 path in both pipelines or a λ3 path in both pipelines. Since the claim is assumed to hold for the shorter pipelines, (λ1 λ2 )∗ and (λ2 λ1 )∗ must be critical λ0 and λ3 paths respectively. Thus the claimed path must be a critical path of the ring of length 2n + 2. 2 28 Theorem 5 The dynamic slack (or dynamic threshold) of a pipeline of processes satisfying assumptions 1 and 2 is the sum of the dynamic slack (or dynamic threshold) of the processes on the pipeline. Proof 5 The theorem follows directly from lemmas 10 and 11. For any given type of buffer, clearly from lemmas 10 f and 11, the dynamic slack and dynamic threshold are τ −2b 2τ and τ respectively. For a heterogenous ring, r, we have the constraints that ds(r, τ ) = = P τ − 2bi i 2τ X τ − 2bi 2τ i dt(r, τ ) = = P (49) fi i τ X fi i (48) τ (50) (51) Furthermore, lemma 9 guarantees that no local cycles force the cycle time of the system to be greater than τ . 2 6.2 Processes with more than two channels In this section we will consider the dynamic slack and dynamic threshold of pipelines containing processes with more than two channels. We will state a set of conditions sufficient to show that if the dynamic ranges of all the pipelines in a system intersect, the system can operate at the target cycle time. In the proceeding section, we will adopt the convention that a channel lj is implemented by variables lij and loj , where lij is an input variable to the process and loj an output variable. Assumption 3 It is possible to partition the set of channels in any process P into two sets L and R such that the projection of P onto any pair of channels l ∈ L and r ∈ R results in a process implementing one of the reshufflings section 6.1. For a system S, any pipeline in the system satisfies conditions of section 6.1. Let the channels in L be referred to as the input channels of P , and those in R the output channels of P . We will use the notation i Pj to refer to the buffer obtained by projecting P onto the variables implementing channels li and rj . 29 Path rij ↑ −rok ↑ rij ↑ −rok ↓ rij ↓ −rok ↑ rij ↓ −rok ↓ Delay ≤ δ(rij ↑, roj ↑) ≤ δ(rij ↑, roj ↓) + τ ≤ δ(rij ↓, roj ↑) + τ ≤ δ(rij ↓, roj ↓) # Tokens 0 1 1 1 Path lij ↑ −lok ↑ lij ↑ −lok ↓ lij ↓ −lok ↑ lij ↓ −lok ↓ Delay ≤ δ(lik ↑, lok ↑) ≤ δ(lik ↑, lok ↓) ≤ δ(lik ↓, lok ↑) ≤ δ(lik ↓, lok ↓) (a) Path rij ↑ −rok ↑ rij ↑ −rok ↓ rij ↓ −rok ↑ rij ↓ −rok ↓ # Tokens 1 1 1 0 (b) Delay ≤ f i Pk + b l Pj ≤ fi Pk + bl Pj + τ2 ≤ fi Pk + bl Pj + τ2 ≤ f i Pk + b l Pj Path lij ↑ −lok ↑ lij ↑ −lok ↓ lij ↓ −lok ↑ lij ↓ −lok ↓ (c) Delay ≤ f j Pi + b k Pl ≤ fj Pi + bk Pl + τ2 ≤ fj Pi + bk Pl + τ2 ≤ f j Pi + b k Pl (d) Table 10: Constraints on delays of paths in processes with multiple inputs and outputs Assumption 4 For a process P with multiple input or output channels: • for any pair of output channels rj and rk of P the constraints in table 10(a) are satisfied. • for any pair of input channels lj and lk of P the constraints in table 10(b) are satisfied. • for any pair of input channels li , ll and any pair of output channels rj , rk , the constraints in table 10(c) are satisfied. • for any pair of input channels lj , lk and any pair of output channels ri , rl , the constraints in table 10(d) are satisfied. • for any pair of input channels li , ll and any pair of output channels rj , rk , fi Pj + bk Pl ≤ τ . When these constraints hold, it can be shown, by considering all possibilities, that if all pipelines can simultaneously contain a number of messages greater than their dynamic threshold and less than their dynamic slack, then no local cycles constrain the cycle time to be greater than τ . Similarly, an exhaustive case analysis can be used to show that if the global cycles stated in lemmas 10 and 11 do not constrain the cycle time to be greater than τ , no global cycle constrains the cycle time to be greater than τ . 7 Algorithm for Slack Matching Slack matching is an optimization performed adding buffers to a system in order to reduce the system’s cycle time. In this section we formulate the slack matching problem as a mixed integer linear program (MILP). 30 We will consider systems that consist of processes that can be represented as constraint graphs if all the communication channels are modeled as channels carrying no data. It is assumed that the system being slack matched is closed. If the system is not closed, sources are connected to the system’s inputs, and sinks to the outputs. It is assumed that the environment’s delays are such that the environment does not constrain the cycle time of the system to be greater than the target cycle time, τ0 . We will first state constraints that can be used to determine whether a system is slack matched. From these constraints, we can derive a system of linear equations that must be satisfied in order to slack match a system. A system is represented by a directed graph, G = (V, E), with each vertex representing a process, and each edge a communication channel. We adopt the convention that an edge (u, v) represents a channel such that it is an active channel of process u and a passive channel of process v. For every pair of edges, (a, b) and (b, c) let ds(a bc , τ ) and dt(a bc , τ ) denote the dynamic slack and dynamic threshold of the process b between channel connected to a and that connected c at cycle time τ . Let M (a bc ) denote the number of messages process b contains between channels connected to a and c. The cycle time of a system will be considered to be that of the slowest assignment in the system. Let S ⊂ V denote the set of sources in the system. It is assumed that each source has exactly one output. Similarly, let T ⊂ V denote the set of sinks in the system. It is assumed that each sink has exactly one input. A path in a graph is a sequence of edges, {ei }, such that src(ei+1 ) = sink(ei ). Let |p| denote the length of a path, p. For any path, p, src(p) = src(e0 ) and sink(p) = sink(e|p|−1 ). A cycle in a graph is a path p, such that src(p) = sink(p). We will refer to the closed interval, [dt(a bc , τ ), ds(a bc , τ )] as the dynamic range of process b between channels a and c. 7.1 Necessary and sufficient conditions for slack matching We present necessary and sufficient conditions for the cycle time of a system to be τ 0 , under assumptions 5 and 6. Section 6 presents sufficient conditions on systems of half-buffers for which assumptions 5 and 6 are satisfied. Under these assumptions, a system is slack matched when each of its pipelines and rings can simultaneously contain a number of messages within their dynamic range. Assumption 5 The dynamic slack and dynamic threshold of a pipeline composed of multiple processes are the sum of the dynamic slacks and dynamic thresholds of the processes. Assumption 6 If the number of messages in a pipeline, or ring, is within the dynamic range of the ring, at the target cycle time, τ0 , then the pipeline, or ring, has an execution with cycle time τ0 . 31 A process graph is said to be slack matched when the following system of equations can be satisfied: Sabab = 0 ∀(a, b) ∈ E (52) Sabbc = Sabab + drabc − M (a bc ) + Sbcbc ∀(a, b), (b, c) ∈ E (53) Sabcd = Sabab + drabc − M (a bc ) + Sbccd ∀(a, b), (b, c), (c, d) ∈ E (54) Sabef = Sabab + drabc − M (a bc ) + Sbcef ∀(a, b), (b, c), (d, e), (e, f ) ∈ E : d ∈ reachable(c) (55) Suuuu = −druuu + M (u uu ) ∀(u, u) ∈ E (56) Sbcab = −drabc + M (a bc ) ∀(a, b), (b, c) ∈ E : a ∈ reachable(c) (57) drabc ∈ [dt(a bc , τ0 ), ds(a bc , τ0 )] Ka − Kd = Sabcd ∀(a, b), (b, c) ∈ E (58) ∀a ∈ S, d ∈ T, (a, b), (c, d) ∈ E (59) Note that the variables drabc denote a value in the dynamic range of process b between the channel (a, b) and the channel (b, c). The variables Ka represent the number of messages removed from source a, and Kd the number of messages inserted in to sink d. For any path in the process graph between processes a and f such that the first edge of the path is (a, b) and the last is (e, f ), the sum of Sabef and the number of initial messages in the corresponding pipeline lies within the dynamic range of the path. If there are multiple paths in the process graph between a process a and f such that the first edge of the path is (a, b) and the last is (e, f ), the variables S abef capture requirement that the dynamic range of the corresponding pipelines be such that there exists a number of messages that can be added to all these a–f pipelines so that the number of messages in the pipeline is within its dynamic range. This requirement arises from the fact that if a message is inserted into one of these pipelines, a message is inserted into all of the pipelines. Lemma 12 Satisfying the system of equations (52)–(59) is equivalent to satisfying Sabab = 0 Suvwx = ∀(a, b) ∈ E X drabc − M (a bc ) (60) ∀p : e0 = (u, v) ∧ e|p|−1 = (v, w) (61) (ei (p),ei+1 (p)) =((a,b),(b,c)) Suuuu = −druuu + M (u uu ) ∀(u, u) ∈ E (62) Svwuv = −druvw + M (u vw ) ∀(u, v), (v, w) ∈ E : u ∈ reachable(w) (63) drabc ∈ [dt(a bc , τ0 ), ds(a bc , τ0 )] Ka − Kd = Sabcd ∀(a, b), (b, c) ∈ E ∀a ∈ S, d ∈ T, (a, b), (c, d) ∈ E 32 (64) (65) LemmaProof 12 Consider any path p in G such that src(p) = u and sink(p) = v. If the path consists of one edge, (60)–(61) has the constraint for this path. Assume that for all paths of length n, satisfying (52)–(55) is equivalent to satisfying (60)–(61). Consider a path p of length n + 1. Let e0 (p) = (u, v), e1 (p) = (v, s), and en (p) = (w, x). Let p0 denote the path from v to w such that e0 (p0 ) = (v, s) and en−1 (p0 ) = (w, x). (61) can be rewritten as Suvwx = X drabc − M (a bc ) (66) (ei (p),ei+1 (p)) =((a,b),(b,c)) = druvw − M (u vw ) + X drabc − M (a bc ) (67) (ei (p0 ),ei+1 (p0 )) =((a,b),(b,c)) = Suvuv + druvs − M (u vs ) + Svswx (68) All other constraints are identical in the two sets of equations. 2 Lemma 13 If a system operates at the target throughput, its process graph is slack matched. LemmaProof 13 If a system operates at the target cycle time, there must exist an execution such that, simultaneously • the number of messages in any pipeline in the system is within the pipeline’s dynamic range. • the number of messages on any cycle in the system is within the cycle’s dynamic range. Since each communication channel is used once per cycle, the number of messages on a ring is constant. Furthermore, if there exist two pipelines, π1 and π2 , between a pair of processes a and b, the difference between the number of messages on the two pipelines is constant. (60)–(65) capture these conditions. 2 Lemma 14 If a process graph is slack matched, the corresponding system operates at the target throughput. LemmaProof 14 If a process graph is slack matched, then (52)–(59) are satisfied. Thus, there exists an execution such that the number of messages in any pipeline (or ring) of the system lies within the dynamic range of the pipeline (or ring). By assumption 6, such an execution has cycle time at most τ0 . 2 33 7.2 MILP for slack matching Slack matching is performed by adding buffers along communication channels in such a manner that the constraints (52)–(58) on the resulting system are satisfied. Replacing constraints of the form Sabab = 0 by ones of the form (69) and (70) allows the variables Sabab to take on a value in the dynamic range of a pipeline of Nab buffers. Slack matching a system now reduces to determining values of the variables Nab such that the system of equations (53)–(59) and (69)–(70) is satisfied. Sab ∈ [Nab · dt(b, τ0 ), Nab · ds(b, τ0 )] ∀(a, b) ∈ E (69) Nab ∈ N ∀(a, b) ∈ E (70) Since there may be multiple solutions, any cost function linear in Nab may be used to drive the optimization. 7.3 Generating the MILP The set of constraints for slack matching a system can be computed in O(m2 n2 ) time where m = |E| and n = |V |. Constraints of the form (69),(70), (56) and (58) can be generated in O(m) time by looping over the edges set. It takes O(mn + n2 ) time to generate an n × n matrix R, such that Rij =   0, i ∈ reachable(j) (71)  1, i ∈ / reachable(j) This is done by running n breadth first searches, one rooted at each vertex. In O(n) time, an array can be constructed such that indicates whether a vertex is a source or a sink. There are O(m 2 n2 ) 4-tuple (a, b, e, f ) satisfying the condition (a, b), (b, c), (d, e), (e, f ) ∈ E : d ∈ reachable(c). Given matrix R, constraints of the form (53)–(55),(57) and (59) can be generated by simply looping over all such 4-tuples. Due to cycle time constraints on the internal cycle, the number of channels a process has is usually bounded, and significantly smaller than n. In this case, the constraint can be generated in O(k 4 n2 ) time. 34 IDecode Irpt− Check Ext− Control Router CBUFE MrgI0 MrgExt Spl D0 Spl D1 Int Ctrl CBUFIE PCUL CBUF PCUH IMEM PCNH PCNL PCIH PCIL Figure 4: Lutonium fetch loop 8 Case Studies The algorithm from section 7 was implemented in Modula-3[8] and used with glpsol, a freely available MILP solver. Two large examples were studied, the fetch loop of the Lutonium[7], an asynchronous 8051 microcontroller and a control loop in the fetch unit of the MiniMIPS microprocessor [6]. 8.1 Example I: Lutonium Fetch Loop This algorithm was used to slack-match the fetch loop of the Lutonium micro-controller. Whilst the instruction memory is not implemented as a pipeline of half buffers, it can be modeled as one. The memory is modeled as a stage whose dynamic threshold equals its dynamic slack. The dynamic threshold is determined by the forward latency of the memory. Figure 4 shows the fetch loop of the Lutonium micro controller. Table 11 shows the buffers needed to slack match the system. The table also lists the results of slack matching when performed by hand on the system. Observe, that there are fewer buffers on the byte channel in the pc increment loop when slack matching is performed using this algorithm. 35 Channel ExtControl - CBUFE ExtControl - Router ExtControl - IntCtrl CBUF - IntCtrl Router - SplD1 Router - MrgI0 Router - MrgExt PCNH - PCIH PCNH - PCUH PCNL - PCUL PCIL - PCUL Slack matching buffers (hand) 1 1 1 1 2 1 3 1 1 1 1 Slack matching buffers (MILP) 1 1 1 1 2 1 3 0 1 1 1 Table 11: Slack Matching buffers for Lutonium fetch VA IJ BJ T MPE Figure 5: Control Loop in the MiniMIPS fetch 8.2 Example II: Control Loop of MiniMIPS Figure 5 shows a loop in the fetch of the MiniMIPS. Table 12 shows the buffers required to slack match this loop. It also shows the results when slack matching was performed by hand. Note that extra buffers included when slack matching was performed by hand may be needed because a ring composed of a mixture of half buffers and full buffers was not included when generating the MILP. Channel VA-MPE IJ-MPE Slack matching buffers (hand) 4 4 Slack matching buffers (MILP) 1 1 Table 12: Slack Matching buffers for the control loop in the MiniMIPS fetch 36 9 Conclusion and future work Dynamic slack and dynamic threshold of a buffer have been defined. An algorithm has been presented to slack match systems composed of processes that can be represented as collections on repetitive SLHSE in standard form, given certain assumptions about the dynamic slack and dynamic threshold of these processes. Sufficient conditions have been presented that guarantee that the dynamic slack and threshold of systems of composed of half buffers satisfy these assumptions. This algorithm has been tested on circuits from the Lutonium[7] and the MiniMIPS [6]. For the examples studied so far, solving the MILP has not proved unreasonable. As larger systems are considered, solving an MILP may take excessively large amounts of time. Similar arguments to those in section 6 can be used to provide a class of full buffers such that systems composed of these buffers satisfy assumptions 5 and 6. Since most real systems do not use each channel on every cycle, extending the theory to systems with conditional communications would be interesting. It would be interesting to study systems composed of buffers with different static slack, in particular the case of systems containing both half buffers and full buffers. References [1] S.M. Burns. Performance Analysis and Optimization of Asynchronous Circuits. PhD thesis, California Institute of Technology, 1990. [2] S. Kim and P. Beerel. Pipeline optimization for asynchronous circuits:complexity analysis and an efficient optimal algorithm. In Proc. International Conference on Computer-Aided Design, 2000. [3] C. Leiserson, F. Rose, and J. Saxe. Optimizing synchronous circuitry by retiming. In Third Caltech Conference On VLSI, March 1993. [4] A.M. Lines. Pipelined asynchronous circuits. Master’s thesis, California Institute of Technology, 1995. [5] R. Manohar and A.J. Martin. Slack elasticity in concurrent computing. In J. Jeuring, editor, Proc. 4th International Conference on the Mathematics of Program Construction, Lecture Notes in Computer Science 1422, pages 272–285. Springer Verlag, 1998. [6] A.J. Martin, A. Lines, R. Manohar, M. Nyström, P. Pénzes, R. Southworth, U. Cummings, and T.K. Lee. The design of an asynchronous MIPS R3000 microprocessor. In Proc. 17th Conference on Advanced Research in VLSI, 1997. 37 [7] A.J. Martin, M. Nyström, K. Papadantonakis, P.I. Pénzes, P. Prakash, C.G. Wong, J. Chang, K.S. Ko, B. Lee, E. Ou, J. Pugh, E. Talvala, J.T. Tong, and A Tura. The Lutonium: A sub-nanojoule asynchronous 8051 microcontroller. In Proc. 9th IEEE Intl Symposium on Advanced Research in Asynchronous Circuits and Systems, May 2003. [8] G. Nelson. Systems programming with Modula-3. Prentice Hall, 1991. [9] P. Pénzes. Pipeline composition for asynchronous circuits. unpublished, September 1999. [10] C.G. Wong. High-Level Synthesis and Rapid Prototyping of Asynchronous VLSI Systems. PhD thesis, California Institute of Technology, 2004. 38 A Dynamic Threshold We list the proofs that were omitted in section 5.2. A.1 Proof of lemma 7 Consider any simple cycle, j in the constraint graph of rn . Let ∆j be the delay along this cycle, kj , the number of tokens initially present on the cycle and αj the change in number of tokens on this cycle when a message is added to the ring. Since the ring can operate at the target cycle time, for all cycles in the constraint graph of r n , (3) must be satisfied when there are ds(rn , τ ) messages on the ring. Thus, for m = ds(rn , τ ) − init msg(rn ) all cycles, j, satisfy (14)–(16). Let C(rn ) be the set of cycles in the constraint graph of rn . The dynamic threshold of the ring is determined by  ∆c − k c τ dt(rn , τ ) = init msg(rn ) + αc · τ  (72) where c is a cycle such that ∆c − k c τ ∆j − k j τ = max . αc · τ αj · τ j∈C(rn ) We now express the dynamic threshold of the ri·n in a similar manner. Observe that ring ri·n has i initial messages for each initial message in ring rn . Thus ds(ri·n , τ ) is given by  ∆c 0 − k c 0 τ α c0 · τ   ∆c 0 − k c 0 τ = i · init msg(rn ) + α c0 · τ dt(ri·n , τ ) = init msg(ri·n ) +  (73) (74) where c0 is the cycle such that ∆c 0 − k c 0 τ ∆j − k j τ = max . j∈C(ri·n ) α c0 · τ αj · τ Recall that any cycle in the constraint graph of ri·n can be written as a composition of cycles in rn . Thus (20) - (22) hold. The cycle c0 must have α > 0. Furthermore, from section 2.1.1, only simple cycles need to be considered. Table 1 and (4) show that simple cycles have |α| ≤ 2. If αc0 = 1, then the cycle c† that traverse each edge in cycle c0 twice has αc† = 2 and ∆ † − k c† τ ∆c 0 − k c 0 τ = c . α c0 · τ α c† · τ Thus we can restrict our attention to the case where αc0 = 2. 39 From (20)–(22), we have that ∆ −k τ = P max α c0 · τ vj ·αj =2i c0 i P j c0 vj (∆j − kj τ ) P τ v j · αj (75) j j Note that i, τ and vj are non-negative. From (15) we note that when (75) is maximized, vj = 0 ∀j : αj = 0. P j:αj 6=0 ∆c 0 − k c 0 τ = P max α c0 · τ vj ·αj =2i v j αj  ∆j −kj τ αj  2τ (76) j Note that (76) is maximized when vj = 0 ∀j 6= c, vc = |α2ic | . Thus,   2i (∆c − kc τ ) 2 |αc | · τ   i (∆c − kc τ ) = i · init msg(rn ) + αc · τ dt(ri·n , τ ) = i · init msg(rn ) + (77) (78) cτ This proves the lemma for κn = ∆cα−k c ·τ A.2 Proof of theorem 3 We use the notation rn to denote a ring consisting of n instances of a pipeline π. Recall that def dtring (π, τ ) = lim i→∞ dt(rL(i) , τ ) L(i) In order to prove the theorem, we need to show that for any  > 0, there exists I such that for all i ≥ I, dt(rL(i) , τ ) κh ≤ − init msg(π) + L(i) h In order to prove this, we bound the difference between dt(rn , τ ) and (init msg(π) + κhh ). For n ∈ [j · h, (j + 1) · h], from lemma 7 dt(r(j+1)·n·h , τ ) ≥ (j + 1) · h · (dt(rn , τ ) − 1) 40 (79) Using lemma 7, substitute for the left hand side of the inequality (j + 1) · n · init msg(rh ) + d(j + 1) · n · κh e ≥ (j + 1) · h · (dt(rn , τ ) − 1) (80) n ((j + 1) · init msg(rh ) + d(j + 1) · κh e) ≥ (j + 1) · h · (dt(rn , τ ) − 1) (81) Rewriting (j + 1) · init msg(rh ) + d(j + 1) · κh e ≥ dt(rn , τ ) − 1 (82) From lemma 7, j · h · dt(rn , τ ) ≥ dt(rj·n·h , τ ) (83) Applying the lemma to the right hand side and rewriting, j · h · dt(rn , τ ) ≥ j · n · init msg(rh ) + j · n · κh ≥ n (j · init msg(rh ) + j · κh ) dt(rn , τ ) ≥ j · init msg(rh ) + j · κh (84) (85) (86) Recall that init msg(rh ) = h · init msg(π). Let X = init msg(rh ). Thus,   dt(rn , τ ) X + κh j · (X + κh ) X + κh (j + 1) · (X + κh ) + 2 X + κh − ∈ − , − n h (j + 1) · h h j ·h h   − init msg(rh ) − κh init msg(rh ) + κh + 2 ∈ , (j + 1) · h j·h (87) (88) Thus, for L(i) ∈ [j · h, (j + 1) · h], dt(rL(i) , τ ) init msg(rh ) + κh 2 + init msg(rh ) + κh ≤ − L(i) h j·h (89) h )+κh + h, (90) holds. Recall that L(i) is increasing in i. Thus for all i > I such that L(I) > 2+init msg(r  dt(rL(i) , τ ) init msg(rh ) + κh ≤ − L(i) h A.3 (90) Proof of lemma 8 Using the notation from section 3.2.3, the cycle in the constraint graph of the ring r 2n that limits the minimum number of messages on the ring is a cycle that is either a ρ0 or ρ3 path in π2n . Label this path p. Since r2n has cycle time at most τ , the ratio of the delay along the cycle to the number of tokens on the 41 cycle is less then τ . Consider a pipeline π2n , and its fastest linear execution. During the steady state, the number of tokens on any path varies by at most one. The path p needs to have at least δ(p) τ tokens at some point during any fastest linear execution, where δ(p) is the delay along p. Thus during any fastest linear execution, π 2n must have at least δ(p) τ − 1 tokens. This corresponds to there being at least dt(r 2n , τ ) − 1 messages in π2n at any point during the steady state of a fastest linear execution. A.4 Proof of theorem 4 The proof of this theorem is structured in the same fashion as that of theorem 3. We will bound the difference between mn and dtring (π, τ ) for all n > h. Given a linear execution of r2·(j+1)·h with dt(r2·(j+1)·h , τ ) messages in the ring such that the cycle period of any vertex is exactly τ , an execution of π2·(j+i)·h can be constructed by mapping the state of the k th process on the ring to the k th process on the pipeline. Such an execution of π2·(j+i)·h will have cycle time at most τ . At any point during this execution, there are at least dt(r2·(j+1)·h , τ ) messages in the pipeline. Thus for any n ≤ 2 (j + 1) · h, (91) holds. From theorem 3, dt(r2(j+1)·h , τ ) ≤ (2j + 1) · h · dtring (π, τ ). Thus,(91) simplifies to (92). (92). mn < dt(r2(j+1)·h , τ ) (91) < (2j + 1) · h · dtring (π, τ ) (92) Consider pn : n ≥ 2j · h. mn ≥ m2j·h From lemma 8 mn ≥ 2j · h · dtring (π, τ ) − 1 (93) Thus for any pipeline pn , n ∈ [2j · h, 2 (j + 1) h],   2j · h · dtring (π, τ ) − 1 2 (j + 1) · h · dtring (π, τ ) mn − dtring (π, τ ) ∈ − dtring (π, τ ), − dtring (π, τ ) (94) n 2(j + 1)h 2j · h   −2h · dtring (π, τ ) − 1 2h · dtring (π, τ ) , ∈ (95) 2(j + 1)h 2j · h 1 dtring (π, τ ) + 2h mn − dtring (π, τ ) ≤ n j (96) Note that for any  > 0, there exists N = 1 dtring (π,τ )+ 2h  such that for all n > 2(N + 1)h, mn − dtring (π, τ ) <  n 42 (97) Thus def dtpip (π, τ ) = lim n→∞ mn = dtring (π, τ ) n 43 (98)