IHPEOVING TEE TDBOIJGEPDTOF A PIPELINE BY INSERTION OF DELAYS 'Jaeak H. Pate1 and Edward S. Davidson
Coordimted
Science kb
Uaiverrityof Illinois
Urbaaa. Illinois
61801
m!!!!EY
A pipelinei.
defined to be e collectionof recalled sementr
which can be kept busy rimilwrcel(
flwr
from
remt
tAaaou4 ly . A terk once iaftiated,to se-atfor its execution.
A collisionoccur.
if
two or wre tarkr attempt
to UJO the 3am umot
atthe a- ttpy.
Tha collision
char3cterirtic3of a pipeline
withfnitiatione
are inveatirespect to a schedule of tuk
A lrtbodology
ia praunted
for mdifyiq
tim-d.
colli3ioa
characteristics
with the iusartioaof delays
JO a~
to incruse
the utfILaatioo
of segntr
and ha~oetha throughplt
under appropriate
schadulfng.
I.

Introduction

Pipeline.
armbeeincrusi~gly
c~lllllin myewputare.
rowtimer for achfovf4
hig4 #peed compuutlon at a lwer COJL than would raauit from limply
using higher Jpees electronic
componente. Howvet, in
wet ca3.3
itir
used betauae of a bettar
parfowapar unit coet over Othr
arChit8CtUre3.
A pipaliae‘Jdefinedhue
ir a collectionof raeourcea calladanwants
which can be kept bury rimltaneouely.
A mkonaa initiated.
flarr
from l agmnt to l egmnt for its
axacutiou.
in a prodeterminedwr.
The affectiveMU of tha pipeline
lias in tha fact t&t a uak be iaitiatad
before the completion of JOI
previnuly
initktadtasks resultis@
in hig4 perforrmce
andera
un be rpocial
rather than general purpose
noulting
in low cost. We tam a pipelinein whiahflw pattern., a rinrlq
all tha ta.4. have idaatical
fuMtioa
piwlinr.
In a mltifunation
pipeline
thus
arm two or wra distinct
poaaible flov pattuna a&
uc4 tank uses one of those flow patterm.
fich flw
pattern is idaatifiad
by a function w
and it ba
dirplayedin a rerervationtable, 31x4 aa Figure 1 &
6.

Barr

corrorpolld

to 88-Uend colto uta
A function-.
demoted by a riagle
capitaltin.
(1,~))
lettar,is placed in row i end collllln j (callafterj unitm of execution A tuk with that functionofif

require3
re(pmt
1. w* shall con3i3tontly
U,. X
em e function
nam in riagle function pipeiiaas.
Fi8.6
ia a reservationtable of A nultifunctiou
pipelin4
witi
two dirttnct
flw pattarm
fortwo fwttionr
A l rrd 8.
Iaoursmielwe
asem
that
a task onoe initktaduat flw rynchronoualy without praawption or wait.
There in no reetruction
on the flw patter.,hmver.
In rig. 1, nultiplo
X'J
in a rw may indiaate
cithu
arlw l emnt
or l egnt
reuaaga (feedback).
mltiplaX'r in e colum iadiute parallel
coaputation.
It ia
the rwaaga of a l egmnt which poaee e problem,
a&y,
tuo

or

at

the

more.taeka

Jam

may
act-t
time, rasulting

to ume the l mm 34-t
in * collision.
Howvereven without
any raueage,in ultifuaction
pipaliues
collision
smy occur because of two or mre&

dirttnctflweof
In previous wrk,,eindapaodeat

Woke.

the centrel
problem treatedisto schedule the cash in A IILVAD pipeline
JO aatorchieve high throughput without caueing any collision.
This problem wan ffrrt
inveetiftatedin (11. Subsequent
wrk on this 'Problem is reported in two doctorel

Air

Force)

under

We ah11 first coneidar sfngla
function pipeliaee
use of undaratading,sinca
the notational
cowplaaity
of Iplltifunatiou
PiPelinas
is considerabla.
for.

Sian14 Function

Piwlina3

Urn #tart by invartigatiq
Jcollisioncbamaof a riagla
function pipaliue(rafamd
to3-1~
a3
pipaliuas
in thie and tha following
section).
A NC
intatvalof.
se-t
i. dafirud
to be l tim
iat~~v.1
batwun two reaarvatiolu (X's) of that 88#For example in Fig. 1, alle
by a single
taak.
usam
intervala of so are 2, 3 a& 5. ht p be t4atarirtica

aatof all usage interval3of a piprlina:e.g.,-~1,2,3,5)
for Pip. 1. Claa~ly any two tank. will
cawaa a collision
if and only if thay have the 3~
initiation
time interval
aa one of the usage intwml~.
A Jaquanca of taek iaitiatione
can be complataly
of initiationinterval8
bedescribed by a requencaFor
twnn successive
task3 (also known a3 1atanCY)~
amaple.
tank initktione
at time inrtants
0, 3. 5, 9by the latancy~equeM4
Ild 12 cau be darcribad
An initiationintervalof 0 fr not Petis(3,2,4,3).
intarvalr
l ibl. . ht c be the l t of & fnitktion(not just tha intarvals
be-en
8uccar8fve
inithtiOM)
Thus 5 for the lataaay
l eqaaaae
of a latency
saqueaaa.
(3,2,4,3)
i. (2,3,4,5.6.7,9.11).
If a l ub3equeRce of latancies
appear periodicallyin an infinite
l equaaca, it is texwd
an initiatione.
Thu. a cycle (2,3,2.5)
impliar sn infinite
initiation
sequence (2,3,2,5,2,3.2.5,2,3,2.5,2,...).
A
couuntlatency cycle is a cycle with only one lateRoyluwcy;
e.g.,
cycle
(4).
ht the m,p, of lcycle be defined a3 the sum of the &tencie#in their 12 aad
Thur the period p of cyela (2.3.2.5)
cyole.
p of cycle (4) ie 4. The averaRe lateucv,
La of lcycle

research wao supported
in part by the National
Science Foundation under Grant3 CJ-3%84X
and 1X-40584
end in pert by the Joint Servicea Electronics
Prom
end U.S.

3t.p.

For

tl&iJ

(U.S.Army,U.S.Navy,

An overview of nome related
results andthee;.
i2.31.
a me comprehensive bibliography
can be found in 161.
Our investigation
is frow a differsac
perspective
aad
se&s a methodology for mdffying
the reservation
tableof a given pipeline
30 a3 to increase the utfliaationof regmncr and hence the throughput underappropriate
sahaduling.
Tha pipeline
utlliutfon
ir
If&tadby ita collfaion chrecterirticr
which are e raeult of the u.40
One way of modifying ~34.
patternr of the raguntr.
pattamisby segat
replication.
Another way ie totewve
our assumption regarding the waitingof a taakbatween NO l tepe and provide intaraal
storagebuffarsv4iah
allw
variabledelay betveen
regmnntr
141.
Stillanother way of changing a u-4 pattern is by inaarti~g noacw&tc
seIIpnte, which siqrly provide a fireddelav betwean l om comutation
atapa. It is the modificationof A pipelhby tha UJ. bf noncompute eagIt
irl .wmat8
which fr the conemu of thir paper.
ad that any computation step can be delayad
by imarting uaago of e noncompute eemant, where each X in thereservationtable is considered to be e computationis the ever40 of the kcencierof the cyala.
-10.
ee for cycle (2,3,2,5)
is U/4-3.
Thin

implies

au average,3 tfiv

unite.

initiation

rata

of one tarkevaty

The initiationinterval
ret g of a cycle ia r*ly
the set C of the infinite
initiationraquance
impliedThue ~{4,8.12.16.20...)for cycle (4)by the cycle.
and for cycle (2.3.2,:)
C 1s (2,3,5,7.9.10,12,14.1~,
I.&
C mod E be the met formd
17,19,21,22.24,26....~.

Contracr

DAM-07-72-0259.

132

by raking module p equivalents
between 0 and (p-l) Of
For cycle (2.3.2,s)with p-12,
the elewmtsof c.
G mod 121(0,2,3,5,7,9,10)
and for constant cycle (4)It can be shown that 5 andwith p-4 C mod l-(C).
C mod p oT a cycle have the follwing
simple properties
Tawmberingthat 0 is not a permissible
initiationinterval.
P1.a.

if

g#O then g 6 C mod P e

Bfi~

maximal compatibilityu
is not a subset
If (Zl,Z2,...
rk]

E G Vi>0

b. 0 6 c mod p and ip E C Viz1 always.
P2.if g # 0 then g 6 5 mod P m(p-g) E C md P.
the set H, the compleIt is useful to introduce
integerJ.
ment set of 5 in 4, the Jet of positive
Clearly g mod p - G-g wd p. Where G is the set ofintag4rJ
module p.
consequence of P2.
~3. h 6 g mod p oThan the follwing
(p-h)

E H d

p.

14tAnCy cycle(1) h43 p - A.
It. C
10) and hence the follwiug.
A constant cycle (A) is allwed
by a
1.1:
iff no usage interval
is an integral
arultiple

A COn#t.¶nt

It is helpful
to look at the allowableusage interval
set fl to see what allwablepipelines
can bekta
rwwhichhasanconstructed
for a giVAn Cycle.
X in each of columns tl,t2,...\
be denoted 8s row
e.g., the 2nd rw of pig. 1 is rw 11,
A pipelineis allowed by a cycle if all its row.
2.4).
To construct
an allwablerw we canara allwad.
start
by placing an X in some coltw~ I. We can place
another X in some column j, Only if the usage intervali-j
6 Fl; a third X in sorecolunmk if (i-k1 aad
I j-k I 6 Ii, and JO on.
Waver,
it is convenient
to restrict
the column
numbers to be betveen 0 and (p-l),
and stillretain all
For this,
let us define tvo
the useful information.
elemants i, j 6 5, to be compatible
if li-jl6B
llpod p.
[tlst2,...tk];

The use of the absolute
quantity
can be avoided byusing property
P3 of g md p. Thus we h8V4 the follwing 1eIIDy.
mwo integers
i,j6 “p are compatible
iff
0
mod P E 5 mod P.
Using the definitionof compatibilityor the abovelewm we can form all the compatibility
classes on theof
2 , given a cycle.
A comoatibflfty
class
elwents-P
is one in which each element is compatible
with every
We need to form only theother eleru3nt in the clrss.
(1-j)

to Jome cycle

then the rw[zl,z2,,,.Jk]is al-

This is because by the definition
usage intervals!z -r 1 are alf 1
lwable.
In this way we can produce only a limftad
number of allwable
rows.
However. with the use of'property
P3 end Lewd 2.1 it is possible
to construct
other allwable
rwe as follwe.
Theorem

rws,
rw

2:
Given a cycle with period
and only those rows, are allwed

p, the follwing
by the cycle:(Jl+ilp,il,i2,...

r2+i2pr...jand y cowatfbility

V integers~148~4~(z1,z2....]

of0

the cycle.

mod p is always

L.emm 2.1:

A mnxfmsl comoatibilityof any other compatibility
class.
is a compatibility
class withloved by that cycle.
of cowatibility~allis a direct

An initiationinterval
between two tasks is raid
to be allowablewith respect to a pipeline
if theretasks do not collidein the pipeline.
A Cycle is Allwablewith respect to a pipeline
if all its fnitiaConversely,
we also saytion interval.
are allwable.
that s usage interval
or a pipelineis allovable
with
A colli.fon
reapact
to 8 cycle if no collisionoccurs.
occursin s pipeline
when a cycle is followed
iff(if
and only if) sow initiationintervalof the cycle
Thus a cycle
equals a usage intervalof the pipeline.
is allwed
by a pipeline
iff there are no elJJbJnt3
corn-mDn between the usage intervalset, 5 of the pipeline
and the initiationintervalset, 5, of the cycle;
i.e.,
Thus
& the
iff
1 fl 2 - 1, or equivalently,
iff rz ;.
complement set of C can be describedas the set of allwableusage intervals
with raepact to the given cycle .
By ualng the property
Pl of 5 the allwability
condition
can be reduced to the following
theorem.
Theorem 1: A cycle with period p and initiationinterval
set C is allwad
by n pipeline
with ueage0
interval
set L, fff
Q mod p) fl (g ewl p) - L.

Corollary
pipelineof L.

rS.JpeCt,

claeees.

Consider a problem in which a pipeline,
characterized by its usage interval
eat, is given and one hrcomplete freedom in choosing an allwable
initiation
sequence.
Bounds on the minimum average latency ofsuch sequence. and a branch-and-boundalgorithm
todiscovera minimum average latency allowable
cycle
era
reportedin 111 and 141. Minimum average latency
cycles maximize segment utilixation.
where utilfxation
i3 measured as the percent
of time the segwnt remains
bury.
Hare we consider
the reverse problem.
Newly,
acycle is given and one has complete freedom in chooring any allwableusage pattern.
While the solution
to the former problem is useful for schedulinga givenpipalina.
the solution
to this problem is usefulfardarigninga pipeline
for a given schedule.
Theorem 2
CoeIplately
characterizas
the entire
class of allwabla
pipelines.
We rho11 soon 3.4 that it is possible
toput an upper bound on remnt
utilization
with thehelp of the cwpatlbllity
claJear.
To achieve wxiwm
utilizationof a semnt
for a given cycle, we wat
increase
the number of usages per task: i.e.,
fncreaaa
the number of X’s in a row.
Theorem 2 gives all p03eible allwablerows and it implies that the maximm
number of X’s in any ellweblerow
is Aqua1 to th4
Jise of the largest
compatibility
class.
Thus themaximum achievableutilizationof a segwnt withreepect to a given cycle is the ratio of the size of~1.988 to the average latency
the largest
compatibilityof the cycle.
Example 1: For cycle (l,S),
p-10, average latency
1*-s, 2 mod 10 - (0,l.S)
and hence & mod 10 = [2,3,4,
The meximal compatibility
cl4338J
COntAin::,“‘~‘:!~(0 2 4 6 83 (0 2 4 73
0,2,5,73,
10,3.5,73,{0,2.5,8],(~.~.;.~~,‘and’(~.;,6:B
1 of which the largest has sire equal to 5. Note that claeses containing
0 Are sufficient
to characterize
all Cl4334S since e
conatant may be added ~ndulo p to all elements of acwpatfbility
cker
to produce another compatibilityclans.
Thus by Theorem
2, no allwable
rw hae mOr8
than 5 X’s.
This implies that the maxirmw posrible
segmant utilization
with cycle (1.9) is 5/5-100X.
0
Example 2:

For cycle(2.3.7).

p-12.

.te=12f34,

GclDd 120(0,2,3,5,7,9,10]
and hence gwd
120(1,4,6,6,
111. The maxim.1 compatibility
claere.
containing0
are (0.1).
[0,4,B),(0,6),and (0.11) of vhich thehrgerthas 3 elemnts.
Thus the maximum nwberof
X’s in any allwable
row is 3 which in turn impliae amaxiwm segment utilixationof 3/4-752.
In other words
no allwablepipaline
for cycle (2,3,7) has a segment
0
which is busy more than 757. of the time.
Among cycles

withsame aa, those which allwahigh utilizationand hence mOre economical realization
are clearly
preferable.
Furthermore
they offer mote133

flexibility
in pipeline
de6ign.
Let us define a cycle
to be perfect,
if it allow6 a 1001. segment utilization;
we csne.g., cycle (1,9) of Exasrple 1. Unfortunately
not teat the perfectnessof a cycle without
forming
Hwever,we know a special
the compacfbility
classes.
class of perfectcycleswhich are of considerable
interestin single function
pipelines.
Theorem 3:Allconstant

cycleslatency

Noncommate

Sementsof Fig.

1 by 2 units

pig. 2. The elenvntal
requirethe elcmantal

and XI2 by 1 unit
input

delaysoutputdelaysdl,

is shown in
dZ,

and

dj

d4, d 5. and d6.
NW given some integer
i between 0 and (p-l),
we arein a position
to de&y any step arbitrarilysuch thatths step occurs in a column number equiv8lent
toi
cl#lulo p. Thus given e cycle, we can 6uke any rw cf
a given re6ervstion
table to look like one of the r-6
of Theorem
2; provided of course, the row does nothave more X’s than the siza of the largest
comp6tibilHeace we have the following
icy class of the cycle.
theorem.

4: For a given cycle, a pipeline
can be snde
l llweble
by delaying
somr, of the steps,
iff thenumber of X’s in eech rw of the reservationtable is1666 than or equal to the sire of the largest
compati0
bilitycla6s of the cycle.
Theorem. Corollarys pipeline
iff there

4.1:
For a given constantlatency
can be made allowableby delaying
are no wre
than A X’s in each row

table.

cycle

(a),

so- steps,of the0

An important
isrplicatfonofCorollary
4.1 is that
adding elemental delay6 to a pipeline
one can alweys
fully
utilizes singlefunction
pipelinewith the useof a cycle with constantlatency equal to the msxm
n&ccof X’s occurringin any single row of the reserAall utiliutionof a pipeline
here,
vation table.
wsthat at lea6t one segacnt is busy all the time.
Thus the mexinnrm achievsble
throughputof that pipeOf course complete rede6ign orline is attained.
replicationof aelectcd
sagmsnts to reduce the numberof X’s in a row may allow higher throughput.
by

Example 3:

table of Fig. 1 Is to bemsde
allowable
withreswctto cycle(1.5).
The rerulting
table appears in Fig. 3.- For .cycie (1,s).
p-6, 2 mod 6=(0,1,5)
andhence g mod 61(2.3.4).
The’
suximsl compatibility
classes containing
0 are:
The first
row of Fig. 3 is row(0.2,4)and (0,3].
(0,2,10),which resulted
from the class (0.2.4)
byconstructing
row [0,2,4+p)
as per Theorem 2. The
from class (0.2.4)
and thesecond rev, 11.3.5) reauits
third row, [2,4] resultsfrom class (2,4] C (0,2,4].

0

are alluueble.

P.

Where tiand tjare labels

of

the

columns

in whichdi and dappear.

Clearly,if

di snddJ arecompatible.

they

mo4

In thfs section we consider
the additionof noncompute segments CO a pipeline
to suke it allowablefor
The effectof delaying
somsd computationa given cycle.
6t.p can be displayed
in a reservationtable by writing e ‘d’ before rhe X which is being delayed.
Epch dindicates
one unit of delay called an elementalw.
In the absence of any other informetionon precedence.
W. mat assume that all the steps
in a column rrmst becompleted
before any steps in the next column ere
sxscuted.
Therefore,
if the steps
in column 2 of Fig.
1 sre unevenly delayed, we mast store
the output ofsome steps so that all the outputs are simultaneously
Available
to the steps
fn column 3 of Fig. I.
The
effectof delaying
the step in row 0. column 2 (Xo2)the rows

Cnc6 we have 6 modified
table,
we aced to assign
the elemental
delays to noncompute segwncs.
Noncom-Put.
segments are physicalresources
like any othersegment and may be shared by various elesmatal delays
for their
efficientutilization.
Two elemental delays
di and dj aredefined to be compatfble
if (ti-t,lare perfect.

Pot constant cycle (1). 5 mod p-(O) and thus
Proof:
One can verify
that (O,l,Z,...,
F
p+l,z...Wl)].
(A-l))
is a compatibility
class with 1 elements.
Hence
ths
upperboundon the seg6mnt utilizationis0
L/L - 100%.
III.

Thur allP E 5-d

1
can share one noncompute se-at-t 1 is allowable.
Using
i f
the above definition
we can form the maximal compatibility cla66es of all the elemental
delay6 present in thesolution.
All the ele~nts
of a co6rpatibility
cla6s
can share a single noncompute segmsnt.
NW the problem
reduce6 to the standard covering
problem: i.e.,
finding
the minimum number of compatibility
classe6 which cover
all the elemental
delays.
beceuseinterval

the usageIt

Exsmnle 4: The set of elemental
delays of Fig. 3 isTheir corresponding
calm<dl.d2.dj,d4,d5.d6.d~.
numbers are c3.6.7.8,9,2,3>.
For cycle (1.5). g mod 6
is (2.3.4)(from Ex. 3).
‘nm* Idl.d21e[dl$?,
Id2,
Noting that thethe maximal compatibility
cla66es.
subsets of maximal compatibility
classes are compstibility
clas6es.
one of many possible
minims1 covqrs is(dl,d21,
Id,).
IdsI, ld6), [d3.d,l.
Thus 5 noacomplte
The aasigaement above is shwn
romatsarerequired.
in Fig. 4, where S3 through S, are noncompute sagaand&sidesreducing the number of noncomputese-at8in a solution.
it is also importantto reduce the added
execution
de&y.
The execution
delay of a task in Pig.
1 is 6 units
while in the modified
table of Fig. 4 itis 11 uaits.
In situations
where it often bacasnw~ssary
to empty the pipeline;e.g., due to logiul
dependencies
awng tasks,
the exacutfon
delay of a task
can become an importantparroterfn determining
theTherefore,
we shall take the added
overallthroughput.
axocution
delay as the objectivefunction
to be minia1louable
mi66d . Now the problem of marking a pipelineoan be formulated
as follarr.
inlat I and J be the number of rows and colusm
the given reservationtable.
Let dij and d! be thednumber of elemental
delays to be.inserted
respectivelyof the reservation
at the input and output of a step Xutable.
If no x occurs
in cell(1.j) of the table thensosm other di,
and d;, are defined to be zero.
diJ
caa be set to sero if it occurs betveen two consecutive
Let D be thecomputation
steps which are indivisible.
Then the problem can be form&ladded execution
delay.
ly stated as:P
l4inimi6e

D -subject

to

dij

2 0.

integerthe

con6traint6,

T

The reservation

forwhere,

134

each paircXab,Xac>g is the set of allowable

withc > b.
usage interval6

withrespectto the given

withperioddab = mar (dib)
O&C1

cycle

- dab

sets

p, andthe output
step

Xec.

in thein the reservationtable.
This 8eK can be formed bytdring all pairwise
distances
between an x and a Y
which appears to the right of the X in the same row.
For example, for the reservationtable of Fig. 6, theof

The initiationinterval& wd 41(0.1.3);&&

hB mod 4=(0].

mod 41(1.21;
P4.e.

if

initiation

The properties

mod p and lp E &

if

d0

if

h#O then
Is,

where

P2

VW.

alv6ys.

Vi&

g+LpcxY

then g E S,

b.
P6.

Pl.

mod p * g+ip E &x

c. ifX+YthengE&mDdpo
P5.e.

sets
for cycle
mod 41(2,3] ;es follws.

&O then g E &x

b.OE&

Vl#.

mod -(P-B&$X

mod p.

=dP-OE~=dP.
OE&
h E &xY mod -(p-h)

E +x

mod p,

adp is the complmt

of C& mod p.

inz.

-P
Theorem 5: A cycle is allwed
by a ~ltifunctioa
pipeliae
iff(I;n mod p) n (C+l,Ymod p) -3,
or equivslantly

lff&of function

mod p) C_ I-&

nams

llpd

p,

V X,X

in

the set0in the cycle.

present

of cqtiThe generellutioaof the definition
is strefghtfonmrd,
except that each iat6yr
mat
be suffixedwith en appropriate
funttiontun.
Thus two ehmnts f and j,, such th8t i.j E $ mod

bllityj>i,are seid

Tke following
Theorem
2.
ti

6.1:

to

be comoatfble

aregeneraiL6ations

TWo el~nts

are competible
Thmorem

rws

6:

which
=w

(j-i)

g Ir,

of M

mud p E h

C (i*lP)x,(j+JIP+.

f1,f2,jl,j2.

cksees(Qj,,...).

. .

p.

ij

E 5
0

mod p.

Given e cycle with period p, all
era allwed
by the cycle era:

integersti

2.1 cudix and JY such that

(j-i)

fff

if

posrible] V nonnegative. . and V coqetiblllty
0l’im smximsl coqatibility
classescan be forprd
in e mmner simikr
to the one for single function
pLp6lines.
As ea uumpla
take again the cycle
The alfomd
earlier.
(lA,lB,2A)
whose 5 sets were

that
the
B is the varhble
BMJND, and ',B' indicetss
bound ha6 been exceeded, and 'd' indicatesthat theconstrd.nt(a) has been violated.
Thi6 algorithm
is rams&ably
efficientin ourFor exemple for ore 20 verieble~~~~~~~~:"~k,allOA nodea only IO4 nodes were
exgmnded and an optirplm solution
was obtainedin 40
seconds on an IBM 360167.
For a particularclass ofproblesm, the technique of [S] may be epplicabletoestfmstethe complexityof the algorithm.

lkre we present
the generallaatioas
of most of
the results
and definitionsof the previous
twosections.
The variables
X and Y will
be used in 6ust
of these results,
where X and Y take function
names astheir values: the value6 need not be distinct.
Iet
zxY be the set of usage intervalsof all cX,y> pairs

the setand P3 Can be generalized

Th6 last value of BOIND is the minimum vel~ofthe objectivefunctionover all possible
6olutioa6
andtharefore
the outPut
solutionsmetingthis bound era
all the minissam added delay solutions.
If only one
optimmsolutionis desired,the condition
D(I)%IODND
in Step B3 should be changed to D(l)~OUND.
A complete example with the constraints
and thebacktracktree are given in Pig. 5. The variables,
di,, have been retainedin the figure
for simplicity.

Piuelines&,,

we definethe letencies.
(1A,lB.2A)
are:intervening

Algorithm
B:
xl.
(Initialine~f-0; BOUIPP-(p-1)a.I;
V(l)9;
B2. [Advance) ici+l;or
D3. [Check bounds and coastraintsl
if (V(i)-p)@(i)>BODND) then go to B6; if a completely
asthen go to B!I;
signed con6trafnt
is violated
B4. [Solution
found?] if ice then go to B2 else outpit the solution V(1) through V(n) and D(n);BtXINDWn);
B5. [Try enother value1 V(l>-V(i)+l;
go to B3;
116. [Dacktrackl
1+-l;
if ti0 then go to 85 elsetwminatethe elgoritb.

IUtifunctioa

zA,-(o,l,2,4j,of all <X.D pairs of a cycle,
to be the set
which contains
all intervalsof a cask of type x froma pr8ViouSly
initiatedtask
of type Y. A cycle 16
described
with latencies
SUffiXed with the function
na6m of the task being initiatedwith that latency;e.g.,
cycle (1A,lB.2A). The period p is the sum ofSince all the constraints
are in module p arithvalues betmeen 0 end
metic, dtj need only take integerThus
thesolution
speceofthe ebove problem(p-1).
This places en upper bound on the eddod
is finite.
execution
tima equal to (p-1)-J,
where J is the numberof colu9616 in the re6ervatioa
table.
Moreover,theobjectivefunction
D is aondecreesing
in d
-Se
ij.
properties
suggestthe follwing
branch-and-boundalgorithm
to find all mini6666
added delay 6olutfons.
Let the number of X's la the reservarion
table ben l Ud let the n variables,d
be stored in any erbi11’
trery order in a one diamnsionalarray
V. Let D(1)represent
the value of the objectivefunctionfor givenvelues of V(1) through V(i), with V(l+l)
through V(n)taken to be 0.

IV.

u111,

iatervalsof step xab; dac is the number at the input
The sus6sstion term in each constraintisthe effectof inserteddelay6columns between Xab and Xac.

era:~~,,-(2,31.

Similarly

The constraints
resultdirectly
from Theorem 1.
The term (c-b) is the usage interval
which existed
bethe insertionof any delays.
and Xec before
mean Xabdelays et
The variabledAb is the number of elementalofof usage intervals~+0,2.31,

lwebleusage intONal

Set6

are:

h

vod

49 2) ;

; &,g mxl 41( 1.2.31.
!& 6ud 4-ro.11;& md l-{OJ]The moximpl compatibility
ck66es containing
Ox are:f0A,2A1t [0&,*2~‘3~1t

A compatibility

class

cl69s
of

that

$

if for eachfunction(",,o,.lBl,function.

~",.3~~3,~-

Gl 16 said

CO m.Wth.tthe number of ehments

type in class c1 isgreaterthaa orequal to the number of alemntsof ths Saw fW%CtiOU
type in class E2.
In the above example.
{OA.OB,lB]The
sa6m
definition
cover
each
other.
and (OB.3r.3BJ
for cover applies
and a c~etibility
isationof Theorem

135

Pnrong rws and elso between e rw
NW we have the generalclass.
4.

Theorem 7: For a cycle, a multtfunctlon
pipelinecanbe made allowableby delaying
some computation
steps
iff each row of the reservationtable is covered by at0
least one compatibility
class of the cycle.
Now
it is a simple matterto fornulate
the problem
In a multifunctionof making a pipeline
allouable.
pipeline different
functionshave different
execution
Let D(X) be the added execution
delay tot-s.
functioncan be any function
functionx. The objectiveof the D(X)‘s,
which is nondecreasfng
in each D(X);e.g., some linear
combioationof D(X)‘s with positive
Lot d (X) be the number of elemental
coefficients.
iJ
delays to be inserted
at the input of a step of function
Let I and .I be the number ofrum X in cell(i,J).
toue and columns in the reservationtable.
The edded
execution
delay for a function
X can be expressed asDot)wife

theconstraints

the usage interval
ed as:[ (thesimultaneously.
References

1.

2.

3.
4.
5.

E.S. Davidson,“The designand controlof pipelined function
generators,”
Proc. 1971 Int. IEgg
Networks
and Cowuters,
Oaxtepec,
Conf. on Svstems.
Mexico, January 1971.
L.E: Shar, “Derign and Scheduling of StaticallyConfigured
Pipelines.”
Tech. Report No. 42, Digital
Syetemt Lb.,
Stanford
University,
Sept. 1972.
A.K. Winelow, “Tank schedulingin a class of pipelined systems,”
Report~-633. Coordinated
ScienceLab, Univ. of Illinois-Urbaoa,
Nov.
1973.
E.S. Davidson,
L.E. Shar,
A.T. Themes, and J.H.
Patal,“Effective
Control for pipelined
computers,”
Proc. Cowaon
Spring 1975, pp. 181-184, Feb.1975.
D.E. Rnuth, “Estinuting
the efficiency
ofBacktrack
programs, ‘1 Mathematics of Computation,
Vol.29,no. 129, pp. 121-136. Jan. 1975.

can be writtenfrom Theorem
5,
betweenXab and Yac can be exprees-

distance

0 1 2 3 4 s
Xsexxof Yac from column 0) - (distancefrom column 0)l.

Of ‘acof constraints.

conridered

Thue we have the following

setIntegerAj

and [( L

o.+c

Sl
xx
SlEl%i xx(X) 2 0-dij W+daaW*)

a#1x
cc -.s..

rmrX diJ (XjMab (x)+b)l Wd P-( cOLl<” k&I
E &Y mod p. foreach pairFigure1.

Rerarvation

table

cXab,Yah.

6 we can see that we need construct
only
per pairwithout
regard to the magaitudee of b and c.
The algorithm
to obtain an optimm
soltuionis the same as Algorithm
B.
From property
OM conrtraint

V.

Concluding

Remarks

We have preeented the allowability
characterieticsofall
We know the structureof pipelinerand cycles.
allovable
pipelines
for a given cycle.
It is aaen
tht one can utilize
a pipelinefullyby adding noncompute segments to make it allovablewith raepact
toFor nonperfectcycles,the pipelinea perfect
cycle.
can stillbe nude allowable
if every row of the reearvatfon table is coveredby at leart one comtibility
class of the cycle.
For single function
pipelines,
constant
latamcy
cycles were shown to be perfect.
Thue a siryle
function
pipeline
can alvays be utilized
fully
with
the use of a" appropriate
constuzt
latexycycle.
For
multifunction
pipeliner,
there is no atraightforward procedure to constructa perfect
cycle,
given
a mix of functions
to be executed.
However,
if a cycle
for itr perfectnear
is given, it can alvays be tested
with the use of compatibility
claeaee.
Cycles which
are mast likaly
to be perfect
are those having evenly
spaced task initiations,
as vell as a fairly
regularThme cycles have a -11
setof
patternof functiona.
ininitiationintervals
and hence OM has more freedomFor
the camechoosing an allowableusage interval.
reason, these cycles are also most likelytorequireaemall number of noncompute segments in meking a pipeline allowable.
For
increasing
the throughput
beyond what would
reeultdue to the full utilizationof a pipeline,
sewnt
replicationmust be done.
Segment replicationis also a viable
alternative
to noncompute segments if
For a cost effective
deetgn,the costs are comparable.
segment replication
and additionof delays should be

I,...s,FigureFigure136

2.

Delaying

3.

parallelcomputation

Waking a pipeline
for cycle(1.5)

allowable

steps

9

012345678

10

(L&}

0

1

2

3

4

St
SS

S7

X
X

X

Figure 4. Assignment of elemantal
delays to noncompute segmantr

Figure 6. Reeervation
table
a mltifunction
pipeline

cycle

(2).

H-d

for

2 - (11

Added delay:
D - -~d,,O,dlO~

+ dll

+ do2

Constraints:

Optimumsolutions

Figure

5.

are:'

(1)

(2 +-&-&10)- do0 + do2 + dll)

(11)11 + -boO,dlO)- d10 + dll)

1.

dO0 - d10 - dll

2.

do0 - dll

- 0. do2 - 1.

- do2 - 0. d10 - 1.

Making the pipeline

allowablefor

A branch-and-boundsearchoptirmxs solutions.

137

for

cycle

(2):

mod 2 E (1).

mod 2 E (1).