%!PS-Adobe-2.0
%%Creator: dvipsk 5.58f Copyright
Radical Eye Software
%%Title: cwc.dvi
%%Pages: 6
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%EndComments
%DVIPSCommandLine: dvips -Pthing600 -f cwc.dvi
%DVIPSParameters: dpi=600, compressed, comments removed
%DVIPSSource:
TeX output :1737
%%BeginProcSet: texc.pro
/TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N
/X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72
mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1}
ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale
isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div
hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul
TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if}
forall round exch round exch]setmatrix}N /@landscape{/isls true N}B
/@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B
/FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{
/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N
string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N
end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{
/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]
N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup
length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{
128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub
get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data
dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N
/rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup
/base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx
0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff
setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff
.1 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N
/cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id
gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp
add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add
/gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{
dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1
adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2
idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string
putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval
adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg}
{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{
adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2
chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{]
}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup
length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{
cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin
0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul
add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict
/eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook
known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X
/IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for
65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0
0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V
{}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7
getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}
ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false
RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1
false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform
round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg
rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail
{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M}
B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{
4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{
p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p
a}B /bos{/SS save N}B /eos{SS restore}B end
%%EndProcSet
TeXDict begin
600 600 (cwc.dvi)
@start /Fa 58 122 df38 DIII44 DII48 DIII53
DI65 DII<0107B8FCA0034BEB007F183E141F181E5DA214
3FA25D181C147FAA24AC7FC5EE167E49B512FE
A25EECFC163C4AC318
004A5CAE91C5FC4C5AED7FF0B8
FCA25F3 D71 D<A05DA41F
A25DA47FA292C7FCA25CA25CA303A25CA30F
A25CA33FA25CAFC497EB6FCA25C2
DI76 DIIII82
D97 DIIIIIIIIIIIIIIIIIII
IIIII E /Fb 20 118 df46 D49 DI53 D65
D70 D73 D76 D80 D<DAFFEFE133C013FB6EAE0FC801FFF39
07FC7F07FCA27FA2
6D153C7F7F6D92C7FC6C7EEBFFE014FE6CEBFFF015FF6C15E016FC6C816C6F7E6C826C82
6C6CFED007FA27E
AC5D6C5E6DDA5A01FFEC3FF002F8EBFFE
FC1F92C7FCD8F8F D87 D97 D100 D107 D110 DI114 DIII E /Fc 1 34 df33 D E /Fd 30 125 df24 DI40
DI45 DIIII60
D62 D<3801FFF1F6D7E15EFF81407EC
01FC381FEC8127EA3ECFFFE131F90B5FCEB807E383FF800EA7F
C090C7FC12FE5AA47E007F14FEEBF6CB612FC6C15FE6C14BF0001EBFE1F3A
003FF007FC2 DIIIIIIII108 D110 DI<D87FFEEB3FC0B53801FFF0
1F13FC6C5BECFFF84ACA25C5CA391C8
FCAF007FB512E0B67EA36C5C24 DIII119
D124 D E /Fe 2 104 df102 DI E /Ff 34
126 df40 DIIII48
52 DI<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F00
C7FCAE121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F000B
III108 D110 DIIIIIII119
DII125 D E /Fg 10 58 df48
DIIIIIIIII E
/Fh 19 118 df40 DI<EA03E0EA0FF0EA1FF813FCEA3FFE
A213FFA27EA27EFA2137E13FEEA01FCEA3FF0127FEAFFE0EA7F80
D97 DIIIII
I105 D108 D
110 DII114 DIII E /Fi 10 118 df99 D102 D105
D108 D110 DII
114 D116 D
I E /Fj 4 121 df85 D105
D E /Fk 66 125 df38 D40
IIIIIIIIII65 DIIIIIIIIIIIIIII82 DIIIII97 DIIIIIIIIIIIIIIIIIIII
DI E /Fl 4 121 df<147E49B47ECEFC0
7E137F3F485AAF5B001F5C157E485AA215FE
007F5C90C7FCAAA21403EDFEDEF000
7E013F13EFECF3EC03A0FFF00FF00D800FC133E25
D116 DI120 D E /Fm 14 118 df
67 D<EB7F803803FFF1C003E003F133F6D6C7E6E7EA26E7EEA1F00C7FCA4
EB01FF131FEBFFEA0FF0EA1FC0EA3F15C05AAF
6C133B3A3FFC1E1FF2607FFCFE003C2
D100 DI<151F9039FFF8E3C907E03F03
3A0FC01FFEBC5CEB800F000F5CEBC01F6C6C48C7
FCEBF07C380EFFF01CC9FCAF380FFFFEECFFC06C14F06C14FC48
3EEB007FF007CC5C390FC001F8
C6B51280D91FFCC7FC23 DII110
E /Fn 1 4 df3 D E /Fo 72 125 df11 DIII39 DII43 DIIIIIIIIIIIIIIII65 DIIIIIIII75 DIIIII82 DIII87 D97 DIIII
IIIIIIIIIIIIIIIIIIIIII
I E /Fp 31 118 df49 DIIIII65 D67 DI73 D76 D82 D84 D97 DIIIIIIII108 DIIII114 DIII E /Fq 16 122 df46 D64 D97
D99 DII103 DI108 D110 DI114 D<EB03CFAA003FB612FC
4881B7FCA36C5D2FCB3A3161FEE3F80AE5A9138FE07FE
6DB55A6D5C6D5C6E5B021F1380DA07FCC7FC26 DII121 D E /Fr 1 4
df3 D E /Fs
45 122 df44 DII<14FF381F81FC
01FC133FEB07C0AF8A200
3F15FCA390C8FC4815FEA54815FFB3A46C15FEA56DFCAA26C6CEB
03F0A36C6CEB07ED130F6C6CEB1F806C6CEB3F381F81F89038
07FFEFC2 DIIIII55 DIII65 D
67 D<DB0FFEC013E3A0FFC01FC03E02FFC7EA0F
83D903FCEC03C748EC00FFF49C
01A23FAFA396C7FC485AAD4CB6
12C06C7EA293CA003F171F7FAFA26C7EA26C7E6C7EA26C7E6D
7E6D6C153F6D7E6D6C157F6D6C15E7D903FEEC01C7D900FFECEB0F01DA0FFC
EBFEFE090C7FCDB0FFEC9FC4
D75 D78 DI82
III107 DIIIII114 DIIIIIII
E /Ft 19 118 df45 D65 D68 D76
D<B912C018FEF0FFC019F0C601FCC813FCD93FF8ED0FFF011FFF13FF0737E
737EC0A31BE01A7FA21BF0A91BE0A21AFF1BC0A34F13801B00
614F5A624F5A4F5AF17FE04F5AFCF01FFE943801FFF891B812E096C8FC18F802
F8CCFCB3B3AFCB7FCA44C D83 D97 D99 D101 DII108 DIII114
DIII E end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 600dpi
TeXDict begin
%%EndSetup
%%Page: 1 1
1 0 bop 823 364 a Ft(A)43 b(Data-Stream)g(Language)g(for)g(Proto)t
(cols)822 659 y Fs(R.)32 b(Cla)m(yton) y Fr(\003)2313
659 y Fs(K.)h(Calv)m(ert)517 775 y Fq(clayton@cc.gatech.edu)412
b(calvert@cc.gatech.edu)638 891 y Fs(v)m(oice:)44 b(404)32
b(853)g( b(v)m(oice:)44 b(404)31 b(894)h(
1008 y(fax:)43 b(404)32 b(894)g(4 y(Net)m(w)m(orking)i(and)
e(T)-8 b(elecomm)m(unications)31 b(Group,)h(College)g(of)g(Computing)
623 1290 y(Georgia)e(Institute)j(of)f(T)-8 b(ec)m(hnology)g(,)33
b(A)m(tlan)m(ta,)g(Georgia)63 b()
y(31)32 b(Octob)s(er)h(0 y Fp(Abstract)0 2036
y Fo(The)52 b(trade-o\013)i(b)s(et)m(w)m(een)f(proto)s(col)g(structure)
f(and)0 2149 y(proto)s(col)27 b(p)s(erformance)f(is)g(usually)f
(treated)j(as)g(a)f(bal-)0 2262 y(ancing)h(act,)i(with)e(impro)m(v)m
(emen)m(ts)h(on)f(one)h(side)f(com-)0 2375 y(ing)e(at)h(the)g(exp)s
(ense)f(of)g(the)h(other)g(side.)38 b(The)26 b(pro)5
b(ject)0 2488 y(describ)s(ed)53 b(in)h(this)f(pap)s(er)h(treats)i(the)f
(structure/)0 2601 y(p)s(erformance)40 b(trade-o\013)h(as)g(an)g
(obstacle)g(and)f(elim-)0 2714 y(inates)35 b(it)g(with)e(a)j(com)m
(bination)e(of)i(structuring)d(and)0 2827 y(compilation)42
b(tec)m(hniques.)81 b(The)44 b(structuring)e(tec)m(h-)0
2940 y(niques)e(are)i(based)f(on)g(data-stream)i(computations)0
3052 y(and)22 b(giv)m(e)h(the)g(proto)s(col)g(dev)m(elop)s(er)f(a)h
(con)m(v)m(enien)m(t)g(w)m(a)m(y)0 3165 y(of)49 b(arranging)g(and)g
(implemen)m(ting)e(proto)s(col)i(func-)0 3278 y(tion.)39
b(The)28 b(compilation)e(tec)m(hniques)h(remo)m(v)m(e)i(the)f(in-)0
3391 y(e\016ciencies)42 b(in)m(tro)s(duced)f(b)m(y)h(the)h(structuring)
e(tec)m(h-)0 3504 y(niques)g(and)i(further)f(tailor)g(the)h(co)s(de)g
(to)h(the)f(host)0 3617 y(system,)25 b(pro)m(viding)c(a)i(high)f(p)s
(erformance)g(implemen-)0 3730 y(tation.)0 4054 y Fp(1)135
b(In)l(tro)t(duction)0 4270 y Fo(The)38 b(complexit)m(y)h(of)g
(designing)d(and)j(implemen)m(ting)0 4383 y(proto)s(cols)29
b(is)f(b)s(est)h(dealt)g(with)e(b)m(y)i(mec)m(hanisms)g(suc)m(h)0
4496 y(as)53 b(abstraction)h(and)e(mo)s(dularization.)107
b(Unfortu-)0 4609 y(nately)-8 b(,)47 b(these)c(mec)m(hanisms)f(extract)
i(an)f(execution)0 4722 y(cost)38 b(in)d(the)h(form)h(of)f(run-time)f
(o)m(v)m(erhead)j(\(b)s(ecause)0 4835 y(of)28 b(b)s(oundary)e
(crossings,)i(for)g(example\))g(and)f(lost)h(op-)0 4948
y(timization)c(opp)s(ortunities)e(\(b)s(ecause)j(of)g(information)0
5061 y(hiding,)j(for)i(example\).)p 0
5308 a Fn(\003)138 5340 y Fm(Corresp)r(onding)d(author)2082
1820 y Fo(The)34 b(trade-o\013)i(b)s(et)m(w)m(een)f(proto)s(col)g
(structure)f(and) y(p)s(erformance)52 b(has)h(spurred)e
(researc)m(h)j(in)e(address-) y(ing)k(the)i(balance.)123
b(F)-8 b(or)58 b(example,)65 b(the)58 b Fl(x)p Fo(-k)m(ernel)1992
2159 y(\(Hutc)m(hinson)29 b(and)g(P)m(eterson)i(1991\))h(has)e
(established) y(an)d(e\013ectiv)m(e)j(balance)e(b)m(y)g(pro)m
(viding)e(a)i(quasi-ob)5 b(ject-) y(orien)m(ted)29
b(arc)m(hitecture)h(for)f(proto)s(col)g(soft)m(w)m(are)i(while)1992
2498 y(implemen)m(ting)58 b(e\016cien)m(t)k(in)m(ter-la)m(y)m(er)g
(comm)m(unica-) y(tion)29 b(through)h(subroutine)e(calls.)2082
2730 y(Instead)78 b(of)g(re-balancing)f(trade-o\013)i(b)s(et)m(w)m(een)
y(structure)36 b(and)g(p)s(erformance,)i(w)m(e)f(c)m(ho)s
(ose)h(to)g(elimi-) y(nate)23 b(the)h(trade-o\013)g(b)m(y)f
(dev)m(eloping)g(a)g(soft)m(w)m(are)i(arc)m(hi-)1992
3069 y(tecture)f(for)g(proto)s(cols)f(and)g(a)h(set)g(of)g(asso)s
(ciated)g(com-) y(pilation)41 b(tec)m(hniques.)79
b(The)43 b(soft)m(w)m(are)i(arc)m(hitecture)
y(giv)m(es)27 b(dev)m(elop)s(ers)f(a)h(structure)f(they)h(can)g(use)g
(to)g(con-) y(trol)37 b(complexit)m(y)g(during)f(proto)s(col)h
(design)g(and)g(im-) y(plemen)m(tation,)i(while)d(the)i
(compilation)e(tec)m(hniques) y(eliminate)26
b(the)i(structure)g(and)f(exploit)g(arc)m(hitectural)1992
3746 y(kno)m(wledge)j(to)h(generate)h(high-p)s(erformance)d(co)s(de.)
y(This)19 b(pap)s(er)h(describ)s(es)f(our)i(approac)m(h)g(to)
h(the)f(prob-) y(lem)44 b(of)i(pro)m(viding)e(a)i(structured)e
(w)m(a)m(y)j(of)f(creating) y(high)41 b(p)s(erformance)h
(proto)s(col)g(co)s(de.)77 b(W)-8 b(e)44 b(ha)m(v)m(e)g(de-)1992
4204 y(\014ned)54 b(data-stream)i(based)f(language)h(and)f(imple-)1992
4317 y(men)m(ted)37 b(the)g(asso)s(ciated)h(compiler.)60
b(By)37 b(relying)f(on) y(a)k(data-stream)i(arc)m(hitecture,)j
(w)m(e)c(hop)s(e)e(to)j(exploit) y(the)34 b(natural)e(mapping)
h(b)s(et)m(w)m(een)h(data)h(streams)f(and) y(proto)s(col)51
b(pro)s(cessing,)k(as)c(w)m(ell)g(as)g(apply)f(a)h(n)m(um-)1992
4769 y(b)s(er)c(of)h(p)s(o)m(w)m(erful)f(and)g(e\013ectiv)m(e)j
(data-stream)f(ori-) y(en)m(ted)59 b(co)s(de)g(analysis)e(tec)
m(hniques)h(to)i(generating) y(high-p)s(erformance)28
b(co)s(de.) y(The)f(rest)g(of)g(this)f(pap)s(er)g(describ)s
(es)g(the)h(design)f(de-) y(cisions)j(b)s(ehind)f(the)k
(data-stream)g(language)g(and)f(its) y(compiler)i(\(section)j
(2\),)h(the)e(language)g(and)g(its)f(com-)p eop
%%Page: 2 2
2 1 bop 0 -208 a Fk(Cla)n(yton)27 b(&)g(Calv)n(ert)f(|)i(A)g
(Data-Stream)f(Language)e(for)i(Proto)r(cols)0 91 y Fo(piler)34
b(\(sections)j(3)f(and)g(4)g(resp)s(ectiv)m(ely\),)i(and)d(a)i(dis-)0
204 y(cussion)43 b(of)h(the)g(issues)f(raised)f(b)m(y)i(this)f(w)m(ork)
h(\(sec-)0 317 y(tion)30 b(5.)0 613 y Fp(2)135 b(Design)45
b(Decisions)0 819 y Fo(The)28 b(single)g(most)h(imp)s(ortan)m(t)f
(design)g(decision)f(to)j(b)s(e)0 932 y(made)45 b(is)f(the)i(c)m(hoice)
g(of)f(soft)m(w)m(are)i(arc)m(hitecture)f(to)0 1045 y(apply)30
b(to)i(proto)s(col)g(dev)m(elopmen)m(t.)44 b(After)32
b(the)f(arc)m(hi-)0 1158 y(tecture)e(decision)e(has)g(b)s(een)h(made,)g
(most)h(of)f(the)g(rest)0 1270 y(of)i(decisions)f(follo)m(w)g(along)h
(either)f(from)h(engineering)0 1383 y(or)g(exp)s(edience.)91
1498 y(There)51 b(are)i(n)m(umerous)e(candidate)h(soft)m(w)m(are)h(ar-)
0 1611 y(c)m(hitectures)44 b(a)m(v)-5 b(ailable)43 b(for)g(proto)s(col)
g(soft)m(w)m(are.)81 b(Of)0 1724 y(course,)66 b(ob)5
b(ject-orien)m(ted)59 b(arc)m(hitectures)g(ha)m(v)m(e)g(at-)0
1837 y(tracted)37 b(atten)m(tion)h(\(La)m(v)m(ender,)h(Kafura,)e(and)f
(T)-8 b(om-)0 1949 y(linson)52 b(1992;)69 b(Sc)m(hmidt,)60
b(Bo)m(x,)i(and)54 b(Suda)f(1993\).)0 2062 y(Ob)5 b(ject-orien)m(ted)52
b(structuring)d(mec)m(hanisms,)56 b(ho)m(w-)0 2175 y(ev)m(er,)j(are)52
b(generally)g(an)m(tithetical)g(to)h(con)m(v)m(enien)m(t,)0
2288 y(compile-time)26 b(optimizations)g(and)g(are)h(exp)s(ensiv)m(e)g
(at)0 2401 y(execution)52 b(time,)57 b(although)52 b(some)g(w)m(ork)g
(is)f(b)s(eing)0 2514 y(done)c(on)g(the)g(second)g(problem)f(\(Sc)m
(hmidt,)k(Harri-)0 2627 y(son,)k(and)49 b(Al-Shaer)g(1995\).)101
b(Morpheus)48 b(\(Abb)s(ott)0 2740 y(and)c(P)m(eterson)h(1992\))i(is)c
(an)h(in)m(teresting)g(approac)m(h)0 2853 y(to)26 b(ob)5
b(ject-orien)m(ted)26 b(proto)s(col)f(dev)m(elopmen)m(t.)40
b(Recog-)0 2966 y(nizing)29 b(the)j(ine\016ciency)e(of)h(general)g(ob)5
b(ject-orien)m(ted)0 3079 y(mec)m(hanisms,)36 b(Morpheus)e(tailors)g
(its)g(ob)5 b(jects)36 b(to)f(al-)0 3192 y(lo)m(w)e(for)f(compilation)f
(in)m(to)i(e\016cien)m(t)g(co)s(de.)48 b(It)33 b(is)f(un-)0
3304 y(clear)26 b(ho)m(w)g(far)g(in)m(to)h(implemen)m(tation)d
(Morpheus)i(has)0 3417 y(b)s(een)k(carried.)91 3532 y(F)-8
b(unctional)21 b(computation)h(is)f(another)i(p)s(ossible)c(ar-)0
3645 y(c)m(hitecture,)60 b(one)54 b(tak)m(en)h(up)d(b)m(y)i(the)f(F)-8
b(o)m(x)56 b(Pro)5 b(ject)0 3758 y(\(Co)s(op)s(er,)46
b(Harp)s(er,)g(and)d(Lee)h(1991\),)49 b(whic)m(h)42 b(is)g(ap-)0
3871 y(plying)29 b(the)i(programming)e(language)j(Standard)d(ML)0
3983 y(\(SML\))35 b(to)g(systems)g(soft)m(w)m(are.)54
b(Adopting)34 b(a)h(p)s(o)m(w)m(er-)0 4096 y(ful)40 b(language)j(suc)m
(h)e(as)h(SML)g(to)g(the)g(wide-ranging)0 4209 y(tasks)30
b(required)e(b)m(y)i(system)g(soft)m(w)m(are)i(requires)c(more)0
4322 y(resources)38 b(than)f(w)m(e)h(had)f(to)i(sp)s(end,)f(ev)m(en)g
(if)f(w)m(e)h(re-)0 4435 y(stricted)30 b(atten)m(tion)h(to)h(just)d
(proto)s(col)i(soft)m(w)m(are.)91 4550 y(Data)k(stream)g(arc)m
(hitectures)f(ha)m(v)m(e)h(also)f(b)s(een)f(ap-)0 4663
y(plied)48 b(to)j(proto)s()60 b(the)51 b(most)g(notable)f(example)
0 4775 y(is)36 b(the)h Fj(Unix)g Fo(Streams)g(subsystem)f(\(Ritc)m(hie)
h(1984\).)0 4888 y(Ho)m(w)m(ev)m(er,)29 b(the)d(relation)f(b)s(et)m(w)m
(een)h(Streams)g(and)f(data)0 5001 y(streams)48 b(exists)g(mostly)g(in)
f(name)h(only:)76 b(Streams)0 5114 y(programmers)51 b(deal)g(with)g
(queues)g(of)h(p)s(oin)m(ters)f(to)0 5227 y(bu\013ers,)g(and)c(there)h
(is)e(no)i(Streams-sp)s(eci\014c)f(opti-)0 5340 y(mization)31
b(applied)f(either)h(within)f(or)h(b)s(et)m(w)m(een)i(mo)s(d-)1992
91 y(ules.) y(Nev)m(er)26 b(the)f(less,)g(w)m(e)g(sa)m(w)g(a)f
(n)m(um)m(b)s(er)g(of)g(adv)-5 b(an)m(tages)
y(to)38 b(a)g(data-stream)g(arc)m(hitecture)h(for)e(proto)s(col)g
(soft-) y(w)m(are.)45 b(First,)32 b(it)g(seems)g(easy)g(to)h
(map)e(proto)s(col)h(data) y(pro)s(cessing)e(problems)g(in)m
(to)i(data-stream)h(problems,) y(at)j(least)g(at)g(a)g
(high-lev)m(el.)55 b(This)34 b(view)h(is)g(consisten)m(t)1992
770 y(with)g(others)h(who)g(ha)m(v)m(e)i(found)d(a)i(data-streams)h
(ar-) y(c)m(hitecture)22 b(appropriate)f(for)h(language)h(pro)s
(cessing)e(or) y(digital)28 b(signal)h(pro)s(cessing.)2082
1110 y(The)44 b(second)f(adv)-5 b(an)m(tage)46 b(to)e(data-stream)h
(arc)m(hi-) y(tectures)k(is)f(the)h(w)m(ell)e(established)g
(theory)-8 b(,)54 b(as)49 b(ex-) y(empli\014ed)29
b(b)m(y)i(W)-8 b(ater's)33 b(\(1991\))h(w)m(ork,)f(of)e(transform-)1992
1449 y(ing)24 b(data-stream)i(computations)f(in)m(to)f(more)h(con)m(v)m
(en-) y(tional)30 b(con)m(trol)i(structures)f(suc)m(h)h(as)f
(lo)s(ops.)44 b(A)32 b(third,) y(related,)22
b(adv)-5 b(an)m(tage)22 b(is)e(the)h(lac)m(k)g(of)f(in)m(tricate)h
(data)g(de-) y(p)s(endencies)30 b(due)h(to)i(the)f(streams')h
(orderly)e(and)g(reg-) y(ular)43 b(data)i(handling,)h(making)e
(standard)g(lo)s(op)g(op-) y(timization)39 b(tec)m(hniques)g
(particularly)f(e\013ectiv)m(e)k(and) y(easy)31
b(to)g(apply)-8 b(.) y(Once)69 b(the)f(arc)m(hitectural)h
(decision)e(had)h(b)s(een) y(made,)30 b(the)g(other)h
(decisions)d(fell)h(in)g(line.)39 b(As)30 b(a)g(long-)1992
2466 y(term)24 b(goal,)j(w)m(e)e(w)m(ould)e(lik)m(e)h(to)i(ha)m(v)m(e)g
(the)e(data-stream) y(arc)m(hitecture)39 b(apply)e(to)i(the)f
(en)m(tire)h(proto)s(col)f(stac)m(k.) y(Ho)m(w)m(ev)m(er,)50
b(in)43 b(the)i(initial)c(stages)46 b(of)f(this)e(w)m(ork)h(w)m(e)1992
2805 y(are)36 b(limiting)c(our)k(scop)s(e)f(to)i(proto)s(col)f
(functions.)55 b(A) y Fi(proto)s(col)40 b(function)34
b Fo(is)f(a)i(data)g(op)s(eration)e(applied)
y(during)23 b(proto)s(col)j(pro)s()g(examples)g(of)g(proto)s
(col) y(functions)d(include)f(encryption)i(and)g
(decompression.) y(W)-8 b(e)28 b(in)m(tend)f(to)h(replace)g
(sequences)f(of)h(proto)s(col)g(func-) y(tions)h(with)g(pip)s
(elines)e(of)k(data-stream)g(functions.) y(This)19
b(w)m(ork)i(is)f(b)s(eing)f(carried)h(out)g(indep)s(enden)m(t)f(of)i(a)
y(particular)27 b(proto)s(col)i(subsystem.)39
b(Ho)m(w)m(ev)m(er,)31 b(to)f(pro-) y(vide)g(a)i(realistic)e
(con)m(text)k(for)d(exercising)f(and)h(ev)-5 b(alu-)1992
3823 y(ating)27 b(stream)h(functions,)f(w)m(e)i(are)f(incorp)s(orating)
e(the) y(language)42 b(and)g(compiler)f(in)m(to)i(the)g
Fl(tau)49 b Fo(\(transp)s(ort) y(and)29 b(ab)s(o)m(v)m(e\))j
(pro)5 b(ject)31 b(\(Calv)m(ert)g(1993\).) y
Fp(3)134 b(The)45 b(Language) y Fo(This)23 b(section)i(presen)
m(ts)g(features)g(of)g(the)g(data-stream) y(language)30
b(b)m(y)f(describing)e(a)j(stream)g(function)f(imple-)1992
4774 y(men)m(ting)g(run-length)f(enco)s(ding)g(\()p Fh(rle)p
Fo(\).)41 b(This)28 b(imple-) y(men)m(tation)35
b(of)h(run-length)e(enco)s(ding)g(is)h(exp)s(ository)-8
b(,) y(not)30 b(exemplary)-8 b(.) y(The)29
b(\014rst)f(t)m(w)m(o)j(statemen)m(ts)g(in)c(\014gure)i(1)g(de\014ne)g
(the) y(structure)i(of)h(the)g(input)f(and)g(output)h
(streams.)45 b(The) y(input)36 b(stream)j(is)f(called)g
Fh(src)g Fo(within)e Fh(rle)i Fo(and)g(is)g(a)0 5589
y Fk(V)-7 b(er.)37 b(1.5)3201 b(P)n(age)26 b(2)h(of)g(6)p
%%Page: 3 3
3 2 bop 0 -208 a Fk(Cla)n(yton)27 b(&)g(Calv)n(ert)f(|)i(A)g
(Data-Stream)f(Language)e(for)i(Proto)r(cols)72 270 y
Fg(1)55 b Ff(rle)42 b({)72 370 y Fg(2)142 b Ff(in)43
b(src)f({)72 469 y Fg(3)229 b Ff(unsigned)41 b(byte)h(})72
569 y Fg(4)72 669 y(5)142 b Ff(out)43 b(dst)f({)72 768
y Fg(6)229 b Ff(unsigned)41 b(byte)72 868 y Fg(7)229
b Ff(unsigned)41 b(byte)h(})72 968 y Fg(8)72 1067 y(9)142
b Ff(local)42 b({)33 1167 y Fg(10)229 b Ff(new)43 b(unsigned)d(byte)33
1266 y Fg(11)229 b Ff(cnt)43 b(unsigned)d(byte)33 1366
y Fg(12)229 b Ff(old)43 b(unsigned)d(byte)i(})33 1466
y Fg(13)33 1565 y(14)142 b Ff(new,)42 b(old,)g(cnt)g(gets)g(src,)g
(src,)g(1)33 1665 y Fg(15)33 1765 y(16)142 b Ff(do)43
b(new)f(ne)h(old)f({)33 1864 y Fg(17)229 b Ff(dst)43
b(gets)f(cnt,)g(old)33 1964 y Fg(18)229 b Ff(old,)42
b(cnt)h(gets)f(new,)g(1)33 2063 y Fg(19)229 b Ff(new)43
b(gets)f(src)g(})33 2163 y Fg(20)142 b Ff(or)43 b({)33
2263 y Fg(21)229 b Ff(if)43 b(cnt)f(eq)h(255)g({)33 2362
y Fg(22)317 b Ff(dst)42 b(gets)g(cnt,)g(old)33 2462 y
Fg(23)317 b Ff(cnt)42 b(gets)g(0)h(})33 2562 y Fg(24)229
b Ff(cnt)43 b(gets)f(cnt)g(+)h(1)33 2661 y Fg(25)229
b Ff(new)43 b(gets)f(src)g(})33 2761 y Fg(26)142 b Ff(on)43
b(eos)f({)h(dst)g(gets)f(cnt,)g(old)g(})33 2860 y Fg(27)142
b Ff(})70 3056 y Fo(Figure)30 b(1:)41 b(An)30 b(example)g(data)h
(stream)g(program.)0 3367 y(sequence)j(of)f(unsigned)e(b)m(ytes.)50
b(The)32 b(output)h(stream)0 3480 y(is)44 b(called)h
Fh(dst)g Fo(within)e Fh(rle)h Fo(and)h(is)g(a)g(sequence)h(of)0
3593 y(unsigned)c(b)m(yte)i()49 b(the)44 b(\014rst)f(b)m(yte)h
(in)f(the)h(pair)0 3706 y(giv)m(es)34 b(the)f(data)h(coun)m(t)g(and)e
(the)i(second)f(b)m(yte)h(is)e(the)0 3819 y(data.)87
b(The)45 b Fh(local)f Fo(statemen)m(t)j(de\014nes)e(the)g(name)0
3932 y(and)20 b(t)m(yp)s(es)h(of)g(lo)s(cal)g(v)-5 b(ariables)19
b(accessible)i(only)f(within)0 4045 y Fh(rle)p Fo(.)91
4175 y(The)27 b(m)m(ultiple)f(assignmen)m(t)h(at)i(line)d(11)j(sho)m
(ws)e(ho)m(w)0 4288 y(the)f(input)d(stream)j(is)f(accessed:)40
b(eac)m(h)26 b(app)s(earance)g(of)0 4401 y(the)37 b(input)e(streams)h
(name)h(on)g(the)g(righ)m(t)f(hand)f(side)0 4514 y(of)k(an)g(assignmen)
m(t)g(causes)h(the)f(next)h(unit)e(\(a)i(b)m(yte,)0 4627
y(in)35 b(this)h(case\))i(to)f(b)s(e)f(read)h(from)f(input.)57
b(The)36 b(input)0 4740 y(stream)31 b(is)e(accessed)j(t)m(wice)f(in)e
(line)f(11.)91 4871 y(Line)39 b(13)j(sho)m(ws)e(ho)m(w)h(the)g(output)f
(stream)h(is)e(ac-)0 4983 y(cessed.)52 b(The)33 b(pair)g(of)h(b)m(ytes)
h Fh(\(cnt,)46 b(old\))33 b Fo(is)g(copied)0 5096 y(the)d(output)f
(stream)h Fh(dst)p Fo(;)f(lines)f(18)j(and)e(22)h(ha)m(v)m(e)h(the)0
5209 y(same)g(e\013ect)h(as)e(line)f(13.)91 5340 y(The)44
b(con)m(trol)g(statemen)m(ts)i(follo)m(w)e(the)g(syn)m(tax)h(of)1992
91 y(Dijkstra's)29 b(guarded)h(commands:)40 b(the)30
b Fh(do)g Fo(\(lines)f(12{) y(21\))d(and)f(the)g
Fh(if)g Fo(\(lines)f(17{19\).)42 b(Alternate)25 b(branc)m(hes)1992
317 y(of)d(either)g(a)h Fh(do)f Fo(or)g(an)h Fh(if)f
Fo(are)g(giv)m(en)h(b)m(y)f Fh(or)g Fo(statemen)m(ts)1992
430 y(\(lines)29 b(16{21,)34 b(for)e(the)f Fh(do)p Fo(\);)h(missing)d
(guards)i(default) y(to)g(true.) y(An)43
b(exception)f(handler)f(ma)m(y)i(b)s(e)f(attac)m(hed)i(to)g(a)1992
808 y(statemen)m(t)c(to)g(deal)f(with)f(un)m(usual)f(situations)h
(aris-) y(ing)29 b(during)g(the)i(statemen)m(t's)i(execution.)
42 b(Curren)m(tly) y(t)m(w)m(o)32 b(exceptions)g(are)g
(de\014ned:)41 b(end-of-stream)32 b(\()p Fh(eos)p Fo(\))1992
1146 y(and)h(arithmetic)g(o)m(v)m(er\015o)m(w.)52 b(The)33
b(end-of-stream)h(ex-) y(ception)26 b(o)s(ccurs)h(only)f(on)h
(the)g(input)e()k(writing) y(the)h(output)g(stream)h
(is)e(non-blo)s(c)m(king.) y(The)46 b(exception)f(handler)f
(at)j(line)d(22)i(applies)e(to) y(the)31 b Fh(do)g
Fo(statemen)m(t)i(at)f(lines)d(12{21;)34 b(an)m(y)e Fh(eos)e
Fo(excep-) y(tion)23 b(raised)g(during)f(an)i(input)f(stream)h
(access)i(in)d(lines) y(12{21)34 b(is)d(caugh)m(t)i(b)m(y)f
(line)e(22,)k(and)d(the)i(co)s(de)f(asso)s(ci-)
y(ated)23 b(with)f(the)h(handler)e(is)i(executed)h(\(the)f(last)g(pair)
f(is) y(written\).)39 b(Execution)27 b(then)g(pro)s(ceeds)f
(from)h(the)h(\014rst) y(statemen)m(t)48 b(follo)m(wing)d(the)
h(handler)f(\()p Fh(rle)g Fo(ends,)50 b(in)
y(this)29 b(case\).)42 b(Uncaugh)m(t)31 b(o)m(v)m(er\015o)m(w)h
(exceptions)e(propa-) y(gate)e(out)e(of)h(the)g(stream)g
(function)e(and)h(are)g(lost,)i Fh(eos) y Fo(exceptions)38
b(imply)e(termination)i(whether)g(they)h(are)
y(caugh)m(t)31 b(or)f(not.) y(Not)39 b(sho)m(wn)d(in)g(this)h
(example)g(but)f(also)i(of)f(in)m(ter-) y(est)f(are)f(the)h
Fh(order)e Fo(and)h Fh(global)f Fo(statemen)m(ts.)57
b(The) y Fh(order)28 b Fo(statemen)m(t)2173
3182 y Ff(order)42 b Fe(f)h Ff(p)g(:)87 b(ai)43 b(rle)f(cs)h
Fe(g) y Fo(de\014nes)f(a)g(pip)s(eline)c(named)k
Fh(p)g Fo(consisting)f(of)h(the) y(stream)31
b(functions)e Fh(ai)p Fo(,)i Fh(rle)f Fo(and)g Fh(cs)p
Fo(;)h Fh(ai)f Fo(is)g(the)h(head) y(of)f(the)h(pip)s(e.)38
b(The)30 b Fh(global)f Fo(statemen)m(t) y Ff(global)41
b Fe(f)j Ff(cs)e(unsigned)f(byte)g(4)j Fe(g)
y Fo(declares)k Fh(cs)f Fo(to)i(b)s(e)f(an)g(unsigned)e(4-b)m(yte)j(in)
m(teger.) y(An)m(y)e(stream)h(function)f(in)f(a)i(\014le)f(ma)
m(y)i(access)g(the) y(global)37 b(v)-5 b(ariables)36
b(declared)h(in)g(the)h(\014le.)62 b(The)37 b(data-)1992
4624 y(stream)26 b(compiler)e(assumes)i(global)f(v)-5
b(ariables)24 b(are)j(de-) y(clared)i(elsewhere)h(in)f(the)i
(proto)s(col)f(co)s(de.) y(The)22 b(compiler)e(accepts)k(a)e
(\014le)f(written)g(in)g(the)h(data-) y(stream)h(language)g
(and)f(pro)s(duces)g(an)g(ob)5 b(ject)24 b(\014le)e(suit-)1992
5114 y(able)33 b(for)h(linking)e(with)h(other)h(proto)s(col)h(co)s(de.)
52 b(Eac)m(h) y(pip)s(eline)27 b(de\014ned)i(in)g(the)i
(\014le)e(app)s(ears)h(in)f(the)i(ob)5 b(ject)
y(\014le)29 b(as)i(a)f(C)g(function)f(with)g(the)i(protot)m(yp)s(e)0
5589 y Fk(V)-7 b(er.)37 b(1.5)3201 b(P)n(age)26 b(3)h(of)g(6)p
%%Page: 4 4
4 3 bop 0 -208 a Fk(Cla)n(yton)27 b(&)g(Calv)n(ert)f(|)i(A)g
(Data-Stream)f(Language)e(for)i(Proto)r(cols)232 79 y
Ff(unsigned)40 b(char)i(*)h(pfun\()319 192 y(unsigned)d(char)i(*)h
(src,)319 305 y(const)e(unsigned)g(int)h(srcsize,)319
418 y(unsigned)e(char)i(*)h(dst,)319 531 y(const)e(unsigned)g(int)h
(dstsize\))91 752 y Fo(where)35 b Fh(pfun)f Fo(is)g(the)i(name)f(of)h
(the)g(pip)s(eline.)52 b(The)0 865 y(return)24 b(v)-5
b(alue)25 b(is)f(a)h(p)s(oin)m(ter)f(to)i(the)f(b)m(yte)h(immediately)0
977 y(follo)m(wing)j(the)h(last)h(b)m(yte)g(written)e(in)g
Fh(dst)p Fo(.)0 1282 y Fp(4)135 b(The)44 b(Compiler)0
1491 y Fo(The)22 b(general)g(compilation)f(tec)m(hnique)i(is)e(to)i
(translate)0 1604 y(a)34 b(data-stream)h(program)e(in)m(to)h(a)g(set)g
(of)f(co-routines)0 1717 y(and)e(a)h(sc)m(heduler)f(\(Nak)-5
b(ata)33 b(and)e(Sassa)h(1983\).)47 b(Eac)m(h)0 1830
y(stream)39 b(function)e(is)g(translated)h(in)m(to)g(a)h(co-routine,)0
1943 y(and)22 b(adjacen)m(t)i(stream)f(functions)f(in)f(a)i(pip)s
(eline)d(share)0 2056 y(a)38 b(\014xed-length)f(bu\013er.)63
b(Eac)m(h)38 b(co-routine)g(executes)0 2169 y(un)m(til)f(it's)i(blo)s
(c)m(k)m(ed)g(b)m(y)g(either)f(an)h(empt)m(y)h(bu\013er)e(on)0
2282 y(input)c(or)j(a)f(full)e(bu\013er)h(on)h(output.)58
b(A)m(t)38 b(that)e(p)s(oin)m(t)0 2395 y(it)31 b(transfers)g(con)m
(trol)g(bac)m(k)h(to)g(the)g(sc)m(heduler,)f(whic)m(h)0
2508 y(is)i(resp)s(onsible)e(for)j(pic)m(king)e(the)i(next)h
(co-routine)f(to)0 2621 y(resume.)40 b(The)30 b(sc)m(heduler)f(also)h
(detects)h(termination,)0 2733 y(either)f(normally)e(or)j(through)e
(deadlo)s(c)m(k.)91 2850 y(The)39 b(compiler)f(uses)i(standard)f(issue)
f(tec)m(hnology)0 2962 y(\(Aho,)g(Sethi,)e(and)f(Ullman)f(1986\),)39
b(and)c(consists)g(of)0 3075 y(a)29 b(fron)m(t-end)g(and)f(a)h(bac)m(k)
h(end.)39 b(The)29 b(compiler)e(fron)m(t-)0 3188 y(end)39
b(is)g(written)g(using)f(lex)h(and)h(y)m(acc.)70 b(Within)38
b(the)0 3301 y(compiler)43 b(programs)g(are)i(represen)m(ted)f(as)g
(abstract)0 3414 y(syn)m(tax)j(trees)f(in)f(whic)m(h)g(the)h(no)s(des)f
(are)i(instances)0 3527 y(of)g(C)171 3519 y(+)-15 b(+)344
3527 y(classes.)91 b(The)46 b(fron)m(t)i(end)e(translates)h(the)0
3640 y(data-stream)27 b(constructs)f(in)m(to)g(con)m(v)m(en)m(tional)h
(con)m(trol)0 3753 y(and)g(data)i(structures,)f(and)g(\015ags)g(them)g
(so)g(the)g(data-)0 3866 y(stream-related)45 b(parts)g(can)g(b)s(e)f
(recognized)h(b)m(y)f(the)0 3979 y(bac)m(k)31 b(end.)91
4095 y(The)23 b(compiler)f(has)h(t)m(w)m(o)i(bac)m(k)f(ends,)g(eac)m(h)
g(di\013ering)0 4208 y(from)29 b(the)g(other)h(in)e(the)h(t)m(yp)s(e)h
(of)f(co)s(de)h(analysis)e(done)0 4321 y(and)k(the)h(output)f(pro)s
(duced.)46 b(One)32 b(bac)m(k)h(end)f(|)g(the)0 4434
y(high-lev)m(el)26 b(bac)m(k)i(end)f(|)h(do)s(es)f(host-arc)m
(hitecture)h(in-)0 4546 y(dep)s(enden)m(t)k(analysis)f(and)h(pro)s
(duces)g(Gn)m(u)g(extended)0 4659 y(ANSI)i(C)g(co)s(de)h(\(Stallman)e
(1995\).)55 b(The)33 b(other,)j(lo)m(w-)0 4772 y(lev)m(el)55
b(bac)m(k)i(end)e(do)s(es)g(host-arc)m(hitecture)i(sp)s(eci\014c)0
4885 y(analysis)29 b(and)h(pro)s(duces)f(assem)m(bly)h(co)s(de.)91
5001 y(The)82 b(high-lev)m(el)f(bac)m(k)i(end)f(p)s(erforms)f(host-)0
5114 y(arc)m(hitecture)40 b(indep)s(enden)m(t)e(optimizations)h(suc)m
(h)g(as)0 5227 y(co)s(de)33 b(motion)f(and)g(lo)s(op)f(fusion.)45
b(Co)s(de)32 b(motion)g(\(see)0 5340 y(\014gure)49 b(2a\))i(is)e(imp)s
(ortan)m(t)g(b)s(ecause,)54 b(conceptually)-8 b(,)1992
91 y(eac)m(h)42 b(access)h(to)f(a)g(data)g(stream)g(is)f(preceded)g(b)m
(y)h(a) y(test)29 b(of)f(the)h(asso)s(ciated)g(bu\013er's)e
(state,)j(with)d(con)m(trol) y(transfer)37 b(bac)m(k)h(to)h
(the)f(sc)m(heduler)f(if)g(the)h(state)h(isn't)
y(acceptable.)h(Co)s(de)26 b(motion)f(com)m(bines)h(the)h(tests)g(and)
y(hoists)34 b(them)h(out)g(of)g(the)h(lo)s(op,)f(where)g(they)
g(can)h(b)s(e) y(used)h(to)j(pre-compute)f(an)g(iteration)f
(index)f(for)i(the) y(lo)s(op.)52 b(Lo)s(op)34
b(fusion)f(\(see)i(\014gure)f(2b\))h(is)e(also)i(imp)s(or-)1992
882 y(tan)m(t)i(b)s(ecause,)h(successfully)c(applied,)i(it)g
(eliminates) y(bu\013ering)28 b(b)s(et)m(w)m(een)j(successiv)m
(e)g(stream)g(functions.) y(Once)43 b(the)f(high-lev)m(el)f
(optimizations)g(ha)m(v)m(e)j(b)s(een) y(\014xed)49
b(and)h(implemen)m(ted)f(in)g(the)i(high-lev)m(el)e(bac)m(k)1992
1403 y(end,)25 b(they)f(will)e(b)s(e)i(folded)f(in)m(to)h(the)h(fron)m
(t)f(end,)h(where) y(they)i(can)h(b)s(e)f(made)g(a)m(v)-5
b(ailable)27 b(to)h(the)g(lo)m(w-lev)m(el)f(bac)m(k)1992
1629 y(end.) y(The)60 b(lo)m(w-lev)m(el)g(bac)m(k)g(end)g
(translates)g(a)g(data-) y(stream)46 b(program)h(in)m(to)f
(the)h(host-system's)g(assem-) y(bly)39 b(co)s(de.)72
b(In)41 b(addition)e(to)i(the)g(usual)f(basic-blo)s(c)m(k)1992
2151 y(optimizations,)33 b(the)g(bac)m(k)h(end)f(p)s(erforms)e(t)m(w)m
(o)k(data-) y(streams)55 b(sp)s(eci\014c)f(optimizations:)90
b(it)55 b(maps)g(data) y(streams)39 b(in)m(to)g(the)g(host)g
(system's)g(register)g(set)h(and) y(it)29 b(replicates)h(the)h
(co)s(de)f(to)h(\014ll)e(the)h(register)h(set.)
y(Mapping)36 b(the)h(proto)s(col)g(pro)s(cessing)f(stream)h(in)m(to)
y(the)44 b(host)h(system's)f(register)g(set)h(tak)m(es)h(t)m
(w)m(o)g(steps.) y(The)41 b(\014rst)g(step)h(resolv)m(es)g
(the)g(in)m(terface)h(di\013erences) y(b)s(et)m(w)m(een)e
(adjacen)m(t)i(proto)s(col)d(functions.)72 b(In)m(terface)1992
3125 y(di\013erences)47 b(are)h(expressed)f(in)f(terms)i(of)g(spans)f
(of) y(b)m()42 b(eac)m(h)d(function)d(consumes)h(some)h
(n)m(um)m(b)s(er)f(of) y(b)m(ytes)46 b(on)g(input)f(and)g(pro)
s(duces)g(some)i(n)m(um)m(b)s(er)e(of) y(b)m(ytes)40
b(on)g(output.)70 b(T)-8 b(o)41 b(a)m(v)m(oid)f(excessiv)m(e)h
(bu\013ering,) y(the)35 b(size)f(of)h(the)g(input)e(and)h
(output)h(spans)f(in)f(b)m(ytes) y(should)f(matc)m(h)k()f
(that)h(is,)e(one)h(should)e(b)s(e)h(a)h(m)m(ul-)1992
3802 y(tiple)i(of)j(the)f(other.)68 b(The)38 b(least)i(common)f(m)m
(ultiple) y(serv)m(es)k(when)f(the)h(spans)f(fail)f(to)j(matc)
m(h,)j(but)42 b(mis-) y(matc)m(hes)28 b(quic)m(kly)e(increase)
i(the)f(n)m(um)m(b)s(er)g(of)g(mac)m(hine) y(registers)j
(required.) y(The)60 b(second)g(step)g(to)h(mapping)d(the)i
(proto)s(col) y(pro)s(cessing)50 b(stream)i(in)m(v)m(olv)m(es)
g(assigning)e(the)i(data) y(streams)29 b(to)h(registers.)40
b(The)28 b(parser)h(assumes)g(there's) y(an)k(in\014nite)e(n)m
(um)m(b)s(er)h(of)i(registers)f(a)m(v)-5 b(ailable,)33
b(so)h(this) y(task)j(is)e(easy)-8 b(.)60 b(The)36
b(co)s(der)h(is)e(resp)s(onsible)f(for)i(actu-)
y(ally)d(mapping)g(the)h(data)h(streams)g(to)g(registers,)h(but)1992
5001 y(since)30 b(the)h(in)m(termediate)f(co)s(de)h(has)g(undergone)f
(opti-) y(mizations)35 b(b)m(y)h(the)h(time)e(it)h(reac)m(hes)
i(the)e(co)s(der,)i(the) y(mapping)33 b(is)g(simpler)f(then)j
(if)e(it)i(had)f(b)s(een)g(done)g(b)m(y) y(the)c(parser.)0
5589 y Fk(V)-7 b(er.)37 b(1.5)3201 b(P)n(age)26 b(4)h(of)g(6)p
%%Page: 5 5
5 4 bop 0 -208 a Fk(Cla)n(yton)27 b(&)g(Calv)n(ert)f(|)i(A)g
(Data-Stream)f(Language)e(for)i(Proto)r(cols)438 351
y Fo(a\))k(Co)s(de)f(hoisting:)1404 51 y Fd(do)
y(if)43 b(|buffer|)d()g(0)g(\031)
y(read)f(n)h(bytes) y(i)g(\030)h(i)f(-)g(1)2756
471 y(.) y(.) y(.) y(od)p 388
772 3125 4 v 438 1472 a Fo(b\))30 b(Lo)s(op)g(fusion:)1404
936 y Fd(do) y(.) y(.) y(.)1491
1183 y(f\(data\)) y(write)42 b(n)h(bytes)1404
1409 y(od) y(do) y(read)f(n)h(bytes)1491
1748 y(g\(data\)) y(.) y(.)
y(.) y(od) y Fc(!) y Fd(do)2756
1230 y(.) y(.) y(.) y(f\(data\))2756
1522 y(g\(data\)) y(.) y(.)
y(.) y(od) y Fo(Figure)30 b(2:)41 b(Example)30
b(high-lev)m(el)f(optimizations.)0 2444 y Fp(5)135 b(Discussion)0
2661 y Fb(5.1)112 b(ILP)37 b(and)i(ALF)0 2844 y Fo(Curren)m(t)57
b(thinking)f(on)i(proto)s(col)g(soft)m(w)m(are)h(seems)0
2957 y(dominated)34 b(b)m(y)g(in)m(tegrated)h(la)m(y)m(er)g(pro)s
(cessing)e(\(ILP\))0 3070 y(and)d(application-lev)m(el)f(framing)g
(\(ALF\))j(\(Clark)e(and)0 3183 y(T)-8 b(ennenhouse)32
b(1990\).)50 b(In)m(tegrated)34 b(la)m(y)m(er)g(pro)s(cessing)0
3296 y(revises)g(the)h(notion)f(that)i(monolithic)d(arc)m(hitectures)0
3409 y(are)42 b(go)s(o)s(d)f(for)g(p)s(erformance)f(and)h(mak)m(es)h
(it)f(appro-)0 3522 y(priate)k(for)g(proto)s(col)g(soft)m(w)m(are.)86
b(Application-lev)m(el)0 3635 y(framing)41 b(is)g(an)g(end-to-end)h
(argumen)m(t)h(that)f(appli-)0 3748 y(cations)33 b(are)h(in)e(the)h(b)s
(est)g(p)s(osition)e(to)j(kno)m(w)f(ho)m(w)h(to)0 3860
y(pac)m(k)-5 b(age)27 b(their)d(data)h(for)g(net)m(w)m(ork)g(tra)m(v)m
(el)h(and)e(to)i(deal)0 3973 y(with)j(net)m(w)m(ork)i(corruptions)e(of)
i(their)e(data.)91 4092 y(Compiler-based)62 b(approac)m(hes)i(to)h(p)s
(erformance)0 4205 y(are)33 b(a)g(natural)f(resp)s(onse)g(to)i(the)f
(call)f(for)h(in)m(tegrated)0 4318 y(la)m(y)m(er)49 b(pro)s(cessing.)95
b(Compilers)46 b(can)j(eliminate)f(all)0 4431 y(structure)30
b(when)f(generating)i(co)s(de.)91 4550 y(Application)42
b(dev)m(elop)s(ers)g(wishing)f(to)k(try)e(appli-)0 4663
y(cation)35 b(la)m(y)m(er)h(framing)e(should)f(appreciate)i(the)g(sim-)
0 4775 y(plicit)m(y)d(and)i(p)s(o)m(w)m(er)g(of)g(data-stream)h
(computations.)0 4888 y(In)c(fact,)j(b)s(ecause)d(at)i(least)f(some)g
(of)g(part)g(of)g(the)g(ap-)0 5001 y(plication)k(is)h(in)m(v)m(olv)m
(ed)h(with)f(pro)s(ducing)e(streams)j(of)0 5114 y(data,)32
b(it)f(ma)m(y)g(mak)m(e)h(sense)f(for)g(dev)m(elop)s(ers)f(to)i(apply)0
5227 y(the)24 b(data-stream)i(system)e(to)g(their)f(systems)h(past)g
(the)0 5340 y(net)m(w)m(orking)32 b(part,)h(a)g(claim)e(di\016cult)g
(to)i(mak)m(e)g(|)f(or) y(ev)m(en)k(consider)f(|)g(for)h(most)
g(other)g(proto)s(col)g(dev)m(el-) y(opmen)m(t)30
b(systems.) y Fb(5.2)112 b(W)-9 b(ork)37 b(Status)1992
3004 y Fo(W)-8 b(e)42 b(ha)m(v)m(e)h(implemen)m(ted)d(an)h(initial)d(v)
m(ersion)j(of)h(the) y(compiler)26 b(fron)m(t)i(end)f(and)g(b)
s(oth)g(bac)m(k)h(ends.)39 b(The)28 b(ini-)
y(tial)33 b(lo)m(w-lev)m(el)h(fron)m(t)g(end)f(w)m(as)i(dev)m(elop)s
(ed)e(to)i(exp)s(er-) y(imen)m(t)43 b(with)f(the)i(ideas)e
(asso)s(ciated)i(with)f(mapping) y(data)g(streams)g(in)m(to)g
(register)f(sets)i(and)e(co)s(de)h(repli-) y(cation)34
b(to)h(soak)g(up)e(extra)i(registers.)53 b(W)-8 b(e)35
b(w)m(ere)g(also) y(in)m(terested)f(in)g(demonstrating)g(some)
i(evidence)e(that) y(mapping)29 b(and)h(replication)g(giv)m(e)
h(some)h(p)s(erformance) y(b)s(ene\014ts,)d(whic)m(h)g(w)m(e)i
(w)m(ere)g(able)f(to)h(do.) y(W)-8 b(e)71 b(are)e(curren)m
(tly)f(implemen)m(ting)f(the)i(high-) y(lev)m(el)f(bac)m(k)h
(end)e(to)j(explore)d(host-arc)m(hitecture-)
y(indep)s(enden)m(t)28 b(optimization)h(issues.)2082
4367 y(Once)43 b(w)m(e)g(ha)m(v)m(e)g(dev)m(elop)s(ed)f(the)h(high-lev)
m(el)e(bac)m(k) y(end)27 b(su\016cien)m(tly)-8
b(,)28 b(w)m(e)h(will)c(fold)j(it)f(in)m(to)i(the)f(fron)m(t-end)1992
4593 y(and)h(con)m(tin)m(ue)i(w)m(ork)f(on)h(the)f(lo)m(w-lev)m(el)g
(bac)m(k)i(end.) y Fp(6)134 b(Conclusion)1992
5114 y Fo(This)54 b(pap)s(er)h(describ)s(es)f(a)j(proto)s(col)f(dev)m
(elopmen)m(t) y(subsystem)30 b(based)h(on)g(the)g(h)m(yp)s
(othesis)f(that)i(a)g(data-) y(steam)39 b(arc)m(hitecture)h
(is)e(appropriate)g(for)h(large)g(sec-)0 5589 y Fk(V)-7
b(er.)37 b(1.5)3201 b(P)n(age)26 b(5)h(of)g(6)p eop
%%Page: 6 6
6 5 bop 0 -208 a Fk(Cla)n(yton)27 b(&)g(Calv)n(ert)f(|)i(A)g
(Data-Stream)f(Language)e(for)i(Proto)r(cols)0 91 y Fo(tions)j(of)h
(proto)s(col)f(soft)m(w)m(are.)43 b(A)30 b(data-stream)i(struc-)0
204 y(ture)j(easily)f(maps)g(to)i(the)f(conceptual)g(\015o)m(w)g(of)g
(data)0 317 y(through)c(a)h(proto)s(col,)g(pro)m(viding)e(dev)m(elop)s
(ers)h(with)f(a)0 430 y(natural)f(mo)s(del)f(for)h(their)g(proto)s
(cols)h(and)e(enhancing)0 543 y(the)33 b(idea)g(that)g(application)e
(la)m(y)m(er)j(framing)e(is)g(some-)0 656 y(thing)23
b(an)g(application)f(dev)m(elop)s(er)i(migh)m(t)f(w)m(an)m(t)i(t)f
(con-)0 769 y(sider.)81 b(A)44 b(data-stream)i(arc)m(hitecture)f(also)f
(admits)0 882 y(man)m(y)d(p)s(o)m(w)m(erful)f(and)g(e\013ectiv)m(e)j
(compiler)d(transfor-)0 995 y(mations,)31 b(op)s(ening)f(up)g(the)i(p)s
(ossibilit)m(y)27 b(of)32 b(ac)m(hieving)0 1108 y(high-p)s(erformance)g
(co)s(de)i(through)e(relen)m(tless)h(appli-)0 1220 y(cation)e(of)f(in)m
(tegrated)h(la)m(y)m(er)g(pro)s(cessing.)0 1607 y Fp(References)92
1788 y Fk(Abb)r(ott,)d(M.)f(B.)f(and)h(L.)g(L.)g(P)n(eterson)e(\(1992,)
g(August\).)228 1888 y(A)j(language-based)e(approac)n(h)g(to)i(proto)r
(col)f(imple-)228 1988 y(men)n(tation.)c Fa(Computer)j(Communic)l
(ations)h(R)l(eview)228 2087 y(\(SIGCOMM)j('92)h(Pr)l(o)l(c)l(e)l(e)l
(dings\))h(23)11 b Fk(\(4\),)29 b(27{38.)92 2210 y(Aho,)41
b(A.)d(V.,)k(R.)c(Sethi,)k(and)c(J.)g(D.)h(Ullman)g(\(1986\).)228
2310 y Fa(Compilers,)e(Principles,)g(T)-6 b(e)l(chniques,)35
b(and)g(T)-6 b(o)l(ols)p Fk(.)228 2410 y(Reading,)27
b(Mass.:)36 b(Addison-W)-7 b(esley)g(.)92 2533 y(Calv)n(ert,)26
b(K.)i(L.)g(\(1993,)e(19-22)g(Octob)r(er\).)h(Bey)n(ond)g(la)n(y-)228
2632 y(ering:)52 b(Mo)r(dularit)n(y)35 b(considerations)f(for)i(proto)r
(col)228 2732 y(arc)n(hitectures.)g(In)i Fa(International)h(Confer)l
(enc)l(e)h(on)228 2832 y(Network)g(Pr)l(oto)l(c)l(ols)p
Fk(,)i(San)d(F)-7 b(rancisco,)40 b(Calif.,)h(pp.)228
2931 y(90{97.)25 b(IEEE)h(Computer)i(So)r(ciet)n(y)f(Press.)92
3054 y(Clark,)g(D.)i(D.)g(and)f(D.)h(L.)f(T)-7 b(ennenhouse)28
b(\(1990,)f(24{27)228 3154 y(Septem)n(b)r(er\).)g(Arc)n(hitectural)f
(considerations)g(for)g(a)228 3254 y(new)c(generation)f(of)i(proto)r
(cols.)e(In)h Fa(SIGCOMM)k('90)228 3353 y(Symp)l(osium)47
b(on)g(Communic)l(ation)g(A)n(r)l(chite)l(ctur)l(es)228
3453 y(and)42 b(Pr)l(oto)l(c)l(ols)p Fk(,)i(Philadelphia,)f(P)n(enn.,)g
(pp.)d(200{)228 3553 y(208.)26 b(A)n(CM)i(Press.)92 3676
y(Co)r(op)r(er,)c(E.,)g(R.)h(Harp)r(er,)f(and)g(P)-7
b(.)24 b(Lee)g(\(1991,)f(August\).)228 3775 y(The)44
b(Fo)n(x)f(pro)5 b(ject:)68 b(Adv)-5 b(anced)44 b(dev)n(elopmen)n(t)g
(of)228 3875 y(systems)27 b(soft)n(w)n(are.)f(T)-7 b(ec)n(hnical)27
b(Rep)r(ort)h(CMU-CS{)228 3974 y(91{178,)d(Sc)n(ho)r(ol)h(of)i
(Computer)f(Science,)g(Carnegie)228 4074 y(Mellon)g(Univ)n(ersit)n(y)-7
b(,)27 b(Pittsburgh,)g(P)n(enn.)92 4197 y(Hutc)n(hinson,)j(N.)g(C.)f
(and)h(L.)f(L.)h(P)n(eterson)e(\(1991,)h(Jan-)228 4297
y(uary\).)20 b(The)g Fa(x)10 b Fk(-k)n(ernel:)32 b(An)21
b(arc)n(hitecture)e(for)h(imple-)228 4396 y(men)n(ting)f(net)n(w)n(ork)
g(proto)r(cols.)f Fa(IEEE)23 b(T)-6 b(r)l(ansactions)228
4496 y(on)30 b(Softwar)l(e)g(Engine)l(ering)36 b(17)11
b Fk(\(1\),)29 b(64{75.)92 4619 y(La)n(v)n(ender,)70
b(R.)64 b(G.,)73 b(D.)64 b(G.)g(Kafura,)71 b(and)63 b(C.)h(J.)228
4719 y(T)-7 b(omlinson)30 b(\(1992,)g(Marc)n(h\).)f(Implemen)n(ting)i
(com-)228 4818 y(m)n(unication)70 b(proto)r(cols)g(using)g(ob)5
b(ject-orien)n(ted)228 4918 y(tec)n(hniques.)39 b(T)-7
b(ec)n(hnical)38 b(Rep)r(ort)h(Carnot{060{92,)228 5018
y(Micro)r(electronics)59 b(and)i(Computer)f(T)-7 b(ec)n(hnology)228
5117 y(Corp.,)27 b(Austin,)h(T)-7 b(exas.)92 5240 y(Nak)i(ata,)30
b(I.)h(and)f(M.)g(Sassa)g(\(1983,)f(18)h(Jan)n(uary\).)e(Pro-)228
5340 y(gramming)i(with)h(streams.)f(T)-7 b(ec)n(hnical)31
b(Rep)r(ort)g(RJ)2219 91 y(3751,)19 b(IBM)g(Researc)n(h)e(Lab)r
(oratory)-7 b(,)18 b(San)g(Jose,)i(Cal-) y(ifornia.)2083
315 y(Ritc)n(hie,)38 b(D.)e(M.)f(\(1984,)h(Octob)r(er\).)f(A)h(stream)f
(input-) y(output)29 b(system.)e Fa(A)-6 b(T&T)30
b(Bel)t(l)h(L)l(ab)l(or)l(atories)g(T)-6 b(e)l(ch-)2219
515 y(nic)l(al)31 b(Journal)36 b(63)11 b Fk(\(8\),)29
b(311{324.) y(Sc)n(hmidt,)j(D.,)g(T.)f(Harrison,)f(and)g(E.)h
(Al-Shaer)f(\( 739 y(26{29)22 b(June\).)h(Ob)5
b(ject-orien)n(ted)22 b(programming)g(for) y(high-sp)r(eed)k
(net)n(w)n(ork)e(programming.)f(In)j Fa(USENIX)
y(Confer)l(enc)l(e)50 b(on)f(Obje)l(ct-Oriente)l(d)g(T)-6
b(e)l(chnolo)l(gies)p Fk(,) y(Mon)n(terey)f(,)27
b(California.) y(Sc)n(hmidt,)42 b(D.)d(C.,)j(D.)d(F.)g(Bo)n
(x,)i(and)d(T.)h(Suda)g(\( 1262 y(June\).)30
b(AD)n(APTIVE:)f(A)g(dynamically)f(assem)n(bled)2219
1362 y(proto)r(col)c(transformation,)g(in)n(tegration,)h(and)g(ev)-5
b(al-) y(uation)36 b(en)n(vironmen)n(t.)f Fa(Journal)j(of)g
(Concurr)l(ency:) y(Pr)l(actic)l(e)31 b(and)f(Exp)l(erienc)l
(e)35 b(5)11 b Fk(\(4\),)28 b(269{286.) y(Stallman,)g(R.)g(M.)
g(\(1995,)f(14)f(June\).)j Fa(Using)g(and)i(Port-)2219
1785 y(ing)47 b(GNU)e(CC)i(\(ver.)g(2.7\))p Fk(.)f(Cam)n(bridge,)j
(Mass.:) y(F)-7 b(ree)28 b(Soft)n(w)n(are)e(F)-7
b(oundation.) y(W)g(aters,)35 b(R.)f(C.)g(\(1991,)f(Jan)n
(uary\).)f(Automatic)i(trans-) y(formation)19
b(of)g(series)f(expressions)g(in)n(to)h(lo)r(ops.)g Fa(A)n(CM)2219
2208 y(T)-6 b(r)l(ansactions)36 b(on)g(Pr)l(o)l(gr)l(amming)g(L)l
(anguages)f(and) y(Systems)f(13)11 b Fk(\(1\),)29
b(52{98.)0 5589 y(V)-7 b(er.)37 b(1.5)3201 b(P)n(age)26
b(6)h(of)g(6)p eop
userdict /end-hook known{end-hook}if}