ͳģ͵ķĽ Ͽѧо ժҪ ΪһлѸٷչ, ģͱč , ʹ컹ռͨIJ֍ DzַĽͳģ͵ĵعĸ ˴ģͣãģƣͣCoarse granularity Data Flow Model µһڽģڣHu90еģգ ͣͣãͻۍ ģͣãģƣIJȥʵ⡣`@A` 죰. ԴģۻӦ÷涼õѸٷչ رضʶ˺ܴƶãֱϽ¼ƍ 㵥ԪķʱǴм㣻¼ķʱʱص ʱصⲿڿռϷģDzм㣻ָč ִܲСڲУִʱǴеģʱDzеġʱ ڹ۲߶ԵģҲ˵ʱھԵġ ģͰʶһĿˍ 㷨ľ̬ԣԿ˵ġģ͵ij ֲԽϸʵֵģƱصͨѶõľ޶ʹ Чʵܶ˳ͨٽč ϸͨѶãʹģͳòһŵѸٽ͡֍ ҪԭΪǶԡ׼áһ һԣͳģԸֵ⡰׼á ڣHu88ݡHu90ͨķָɷΪַ ڷDzַǾ·ʽ⡰׼áЩ вַѸֵDzַһֵֻ֪λþͿɍ Ϊ׼áһ⣬˴ģͣãģƣ͍ Coarse grunularity Data Flow ModelԴͳģ¸Ľ . Ĵԣ . ķǴԣ . ڲ״̬ . ڿģͣĸعĴͳ⣺ δֵ֮ǰǿԷʵģ . ĸĽɲֵ ģͣãģƣͲгֲеʣһͨѶõ͵ŵ㡣ĿǰѸٷչġվһơ ĵĽṹģ죱. ͳģ͵IJ֮죲. ģ͍ ãģƣ͵Ķ壻죳. ãģƣ͵Ӧ÷ʵ `@p` 죱. ͳģ`@A` ͳģΪ㷨ľ̬ԣ ԾִеȺȻģԼǶߍ ±ԣģIE82ݣ ʣ. ϸԣÿֻһ򵥵߼㡣 ʣ. ĺԣûڲ״̬һ ĺпϣtokensڵǰпϡ ʹģ;㹻ļֵIJԣĿǰ ʣģAN86ݡSK86ݣǣҲ ʣʹľԺܴҪͨѶõ ±һ һϸԵ˾޶ͨѶ ڴͳģУΪ㷨ľ̬ԣһ񣨽 㣩һָǣＫطֹ׷ϸڵģУ Ϊ˱ȷԣ뻨ʱȥĹݵƵ ݺͷԸɶ㡢ִкԱͬԵȵȡ ǰ㷨ٶȿ죬ɥʧ˲е塣һָǣ ģ͵ϸԣʹĿǰӲ£Чʵ Ϊ˿˷־ԣǽôģͣͨ۸ ָĹģγɺ㡣ϸȣȸʺڵǰč ׼ΪеĺܶദܹԽϸߵЧִ֧ȣJD89ݍ һģ͵ľӦáĽһǶ̽ڴѰ ϸߵЧʡ ȴDzַʹִе޷ִ Hu88ݡHu90ݵĹ󣨲ɷΪ ַDzַPostʽ a`-`1`!`X`-`1`!`a`-`2`!`X`-`2`!`b`-`1`!`X`-`2`!` 󣩍 a`-`1`!`,X`-`1`!`,a`-`2`!`,X`-`2`!`ɷΪ`-`1`!`a`-`1`!`,a`-`2`!`ͦ`-`2`!`X`-`1`!`,X`-`2`!``-`1`!` ã b`-`1`!` ֵ b`-`1`!`, X`-`2`!` ˳򡣶 `-`2`!`ֻһ壬вáִֻ ֪ a`-`1`!`,a`-`2`!` ֵX`-`1`!` X`-`2`!` ֵݲǣΪݹȥ A=B+I, Ϊ n ׷󣬣Ϊ n ׵λǿɽеԪ Ϊ飺`-`1`!`b`-`ii`!` | i=1,,n`-`2`!`b`-`ij`!` | ij Ц`-`1`!`Ϊ ַ`-`2`!`ΪDzַҪ A=B+I 㣬ֻ֪`-`1`!`еֵ`-`2`!` еֵʱΪݹȥвַDzַĻ֡ Ӧüһоɲ [1][Hu88][Hu90] ϷڴԾôͳġǽʹ ñִе޷ִСDZĽԴﵽ ʶ ĺԽٶȣ˲ҪͨѶʩ ͳģͼУһĺпϽ뵱ǰ пֵйأýǰļ޹أǿԳƴͳģ͍ ĴΪ޼ԡΪһ򵥵ӣ f(n)=n! ļڴͳ ģпͼ1(a) ʾͼи㶼޼ԣرضڡ˷ ҲˡʹΪ˱ǰʹһؽΪ ϢͼĸԣͬʱҲģΪ ͬͨѶáмԣǿԹͼ(b) ģ ͼڡ˷*ڲ״̬жǷΪ ӶǷʵϣʱ˷*һд洢ԍ ͼ1(a) Ƚϣͼ1(b) δ㷨ľ̬ԣԵč ԽԣͨѶ豸ϳ˶ݴ뷴Ӷɴӿƍ ٶȡ n n Щ Щ ة ة Ⱥϲũ Ⱥϲũ Щ Щ ة ة ȿ ȿ ة ةة ة ة ȼ ˷* Щ Щ Щ ة ة ة ȿ ة ЩЩ T F ة (a) (b) `@M` ͼ. ׳˵ļͼ`@A` . ľ ͳģͷΪ֡ģУ ܶҽӦпϵýĸ뻡ϡ䡰If f`-`1`!`(1) then f`-`2`!`(2) else f`-`3`!`(3)ͼ.ĺʾýɶ f`-`1`!`, f`-`2`!` f`-`3`!` ıֱֵ𵽴ﻡ123ʵϣж f`-`1`!` Ϊ棬򻡣 f`-`3`!` ıõģ f`-`1`!` Ϊʱf`-`2`!` ıލ õġΪбҪȡֵĹ ةةة Щ `@M` ͼ `@A` ĵ˴ͳģ͵һЩķ档ҪĽ Щһǿ϶ģǾDzôģ͡˵ߴ֍ ģ͵Чʣһֵֵ̽⣬˵Բò βĸҲԲöֵݹ麯Ľһֵǣ µģԲôԡڲ״̬ȵȸ˷ĵ㲻㣬 嶨彫ü뷱½ǽԸһģ͡ `@p` 죲. ģͣãģƣ`@A` ͳģУһͼɽ㲿ͨɣͨӍ 㡣ÿͨԲ֮ͬ֡ԼͨѸͨڍ ͨϴʵֵģͨϵԶеķʽеģFIFO ͨɷΪࣺ . ⲿͨͼݣ . ڲ֮ͨ䴫ݣ . ⲿͨ緢ݡ ͼĶͨ·ʽеģͨϵͬʱ ͨϲݡ һĴͼСͼ϶ɵģϷʽȽϼ򵥣ֻҪ ⲿͨⲿͨͬĽкϲɡͼ3(a)ͼ3(b)č ͼϲɵͼ3(c) ͼ Ϊ˱⴫ͳģеϸԺʹԣ޼ԣɽÿ ɴд洢Զý㲻򵥵߼ƍ 㣬һΪӵ㣻дԣҾʷ ԡͬʱΪٶȣȴDzַĸÿ a b c b a c ةة ة ةة ة `-`1`!` + `-`2`!` = `-`1`!` `-`2`!` Щ ЩЩ Щ ЩЩ c d a d (a). (b). (c). `@M` ͼ. ͼĺϲ `@A` ֮ͨһڶֵһд ҲòֵĹʽж売. ע¸ڣٶã`-`1`!`ʾݼã`-`2`!`ʾĵַϣ ֱʾ`-`1`!`ȣ`-`2`!` 売. p ʽ涨ʮԪ I`-`p`!`, R`-`p`!`, W`-`p`!`, O`-`p`!`, S`-`p`!`, s`+`0`!``-`p`!`, q`-`waitp`!`, Register`-`p`!`, G`-`p`!`, FSУ I`-`p`!` ͨΪͨ R`-`p`!` Ƕַַͨߵĸںܣ W`-`p`!` дַͨ O`-`p`!` ͨΪͨ S`-`p`!` ״̬ s`+`0`!``-`p`!` dzʼ״̬s`+`0`!``-`p`!`S`-`p`!` q`-`waitp`!` ǵȴ״̬q`-`waitp`!`S`-`p`!` Register`-`p`!` ǣڲĴ G`-`p`!` ǵ𼯣ֵ򼯺ϵIJ (1). (2). (3). `-`in`!` Ǵ I`-`p`!` {} V ӳ䣻`-`register`!` Ǵ Register V ӳ䣻s, s'S`-`p`!`\{q`-`waitp`!`}`-`R`!` Ǹýȴ״̬ʱȴı ַ V`-`1`!` ӳ䣻`-`out`!` Ǵӣ`-`p`!` ֵӳ䣻`-`W`!` Ǹýĵ ַ`-`1`!`ӳ䡣 ±߶Ըֱ۽ͣ . p ״̬ sÿͨin`-`i`!` ϵĵһֵסͨǣƣɣƣ϶У `-`in`!`(in`-`i`!`) ʱɱ ģĸͨ in`-`i`!` ϵֵ `-`in`!`(in`-`i`!`)ÿ ͨ out`-`j`!` ϲ`-`out`!`(out`-`j`!`)ŵ out`-`j`!` Ķȥȫֱ ֵ `-`w`!` ʽͨдͨд洢У p ״̬ s' . ״̬ÿ ͨin`-`i`!`ϵĵһֵǦ`-`in`!`(in`-`i`!`) ʱɱ𡣵ܿڱ IJַһЩԱʽַ͹ģδֵ εֻǽȴ״̬ q`-`waitp`!`ͨ in`-`i`!` ϵֵ`-`in`!`(in`-`i`!`) ԭ״̬ s Ԧ`-`register`!` ʽڲĴ Register Сȴ״̬ Ľ㲻ٱͨϵֵ . ȴ״̬Ľ p, ͨͨȥȴĸǷѸֵѸֵý ͨͨҶֵڲĴ Register б ǰֵԭ״̬ͨ out`-`j`!` Ķβֵ`-`out`!`(out`-`j`!`), ȫֱֵ `-`w`!` ʽͨдͨд洢У ״̬' עԱĸƹ㣬δֵ֮ǰǿԷʍ ġ ƣǶԵĺҪ󼯣Ҫھģ͡磬ڍ ģпҪڣ־мȴ״̬ʹ㷢ĵڣ ֲȴ״ֱ̬ӵݵģҲ˵ijЩַ ͨԱʽ͹ʹȴ״̬ȴЩֵ ֵ֮󼤻ֵӦ͵һβֵַͨč ʽ͹ʹԵһַʽֵͬڲַ ͬ£ Ϊ˱﷽㣬Ժӳͼʾӳ䱾ã(a`-`1`!`, b`-`2`!`), (a`-`1`!`, b`-`2`!`)ݱʾӳ䣺a`-`1`!`b`-`1`!`, a`-`2`!`b`-`2`!` [f; (a`-`1`!`, b`-`1`!`), , (a`-`n`!`, b`-`n`!`)] ʾӳ f: a`-`i`!`b`-`i`!` . ͼһĹ涨 a`-`1`!` X`-`1`!` a`-`2`!` X`-`2`!` R ةةةة W Register, et al ЩЩ b`-`1`!` X`-`02`!` `@M` ͼ. Ӧa`-`1`!`X`-`1`!`a`-`2`!`X`-`2`!`b`-`1`!`X`-`2`!`Ľ p `@A` ʽ涨£ I`-`p`!`={a`-`1`!`, X`-`1`!`, a`-`2`!`, X`-`2`!`} R`-`p`!`={R} W`-`p`!`={W} O`-`p`!`={b`-`1`!`, X`-`02`!`} S`-`p`!`={s`+`0`!``-`p`!`, q`-`waitp`!`}; s`+`0`!``-`p`!` Ϊʼ״̬; q`-`waitp`!` Ϊȴ״̬; G`-`p`!`=G`-`1`!`G`-`2`!`G`-`3`!` G`-`1`!`={| `-`in`!`=[(a`-`1`!`, x`-`1`!`), (X`-`1`!`, y`-`1`!`), (a`-`2`!`, x`-`2`!`), (X`-`2`!`, y`-`2`!`)], `-`out`!`=[(b`-`1`!`, u=x`-`1`!`+x`-`2`!`), (X`-`02`!`, y`-`2`!`)], `-`w`!`=[(address(u), u=x`-`1`!`+x`-`2`!`)], x`-`i`!`V`-`1`!` and y`-`i`!`V}; G`-`2`!`={| `-`in`!`=[(a`-`1`!`, x`-`1`!`), (X`-`1`!`, y`-`1`!`), (a`-`2`!`, x`-`2`!`),(X`-`2`!`,y`-`2`!`)], `-`Register`!`=[(r`-`1`!`, x`-`1`!`), (r`-`2`!`, y`-`1`!`), (r`-`3`!`, x`-`2`!`), (r`-`4`!`, y`-`2`!`), (r`-`5`!`, s`+`0`!``-`p`!`)], (y`-`i`!`V)( t((x`-`t`!`V`-`2`!`)((it)(x`-`i`!`V))), i=1, 2}; G`-`3`!`={| `-`Register`!`=[(r`-`1`!`, x`-`1`!`), (r`-`2`!`, y`-`1`!`), (r`-`3`!`, x`-`2`!`), (r`-`4`!`, y`-`2`!`), (r`-`5`!`, s`+`0`!``-`p`!`)], (x`-`1`!`V`-`2`!`x`-`2`!`V`-`1`!`)(`-`R`!`=[(x`-`1`!`, z`-`1`!`)]Ħ`-`out`!`=[(b`-`1`!`, u=z`-`1`!`+x`-`2`!`), (X`-`02`!`, y`-`2`!`)] Ħ`-`w`!`=[(adress(u), u=z`-`1`!`+x`-`2`!`)]); (x`-`1`!`V`-`1`!`x`-`2`!`V`-`2`!`)(`-`R`!`=[(x`-`2`!`, z`-`2`!`)]Ħ`-`out`!`=[(b`-`1`!`, u=x`-`1`!`+z`-`2`!`), (X`-`02`!`, y`-`2`!`)] Ħ`-`w`!`=[(adress(u), u=x`-`1`!`+z`-`2`!`)]); (x`-`1`!`V`-`2`!`x`-`2`!`V`-`2`!`)(`-`R`!`=[(x`-`1`!`, z`-`1`!`), (x`-`2`!`, z`-`2`!`)]Ħ`-`out`!`=[(b`-`1`!`, u=z`-`1`!`+z`-`2`!`), (X`-`02`!`, y`-`2`!`)]Ħ`-`w`!`=[(adress(u), u=z`-`1`!`+z`-`2`!`)]), x`-`i`!`V, z`-`i`!`V`-`1`!`} ƣӺ 򣱣 (`-`Register`!`=[(r`-`1`!`,x`-`1`!`), (r`-`2`!`, y`-`1`!`), (r`-`3`!`, x`-`2`!`), (r`-`4`!`, y`-`2`!`), (r`-`5`!`, s`+`0`!``-`p`!`)] (x`-`1`!`V`-`2`!`x`-`2`!`V`-`2`!`)) (((q`-`waitp`!`,`-`Register`!`,`-`R`!`, s`+`0`!``-`p`!`, `-`out`!`,`-`w`!`)G`-`3`!`) ((s`+`0`!``-`p`!`,`-`in`!`, s`+`0`!``-`p`!`, `-`out`!`,`-`w`!`)G`-`1`!`)) `-`R`!`=[(x`-`1`!`, z`-`1`!`), (x`-`2`!`, z`-`2`!`)],`-`in`!`=[(a`-`1`!`, z`-`1`!`), (X`-`1`!`, y`-`1`!`), (a`-`2`!`, z`-`2`!`), (X`-`2`!`,y`-`2`!`)] 򣲣 (`-`Register`!`=[(r`-`1`!`,x`-`1`!`), (r`-`2`!`, y`-`1`!`), (r`-`3`!`, x`-`2`!`), (r`-`4`!`, y`-`2`!`), (r`-`5`!`, s`+`0`!``-`p`!`)] (x`-`1`!`V`-`2`!`x`-`2`!`V`-`1`!`)) (((q`-`waitp`!`,`-`Register`!`,`-`R`!`, s`+`0`!``-`p`!`,`-`out`!`,`-`w`!`)G`-`3`!`) ((s`+`0`!``-`p`!`,`-`in`!`, s`+`0`!``-`p`!`,`-`out`!`,`-`w`!`)G`-`1`!`)) `-`R`!`=[(x`-`1`!`, z`-`1`!`)],`-`in`!`=[(a`-`1`!`, z`-`1`!`), (X`-`1`!`, y`-`1`!`), (a`-`2`!`, x`-`2`!`), (X`-`2`!`,y`-`2`!`)] 򣳣 (`-`Register`!`=[(r`-`1`!`,x`-`1`!`), (r`-`2`!`, y`-`1`!`), (r`-`3`!`, x`-`2`!`), (r`-`4`!`, y`-`2`!`), (r`-`5`!`, s`+`0`!``-`p`!`)] (x`-`1`!`V`-`1`!`x`-`2`!`V`-`2`!`)) (((q`-`waitp`!`,`-`Register`!`,`-`R`!`, s`+`0`!``-`p`!`,`-`out`!`,`-`w`!`)G`-`3`!`) ((s`+`0`!``-`p`!`,`-`in`!`, s`+`0`!``-`p`!`,`-`out`!`,`-`w`!`)G`-`1`!`)) `-`R`!`=[(x`-`2`!`, z`-`2`!`)],`-`in`!`=[(a`-`1`!`, x`-`1`!`), (X`-`1`!`, y`-`1`!`), (a`-`2`!`, z`-`2`!`), (X`-`2`!`,y`-`2`!`)] ֱϽͼжӦ a`-`1`!`X`-`1`!`a`-`2`!`X`-`2`!`b`-`1`!`X`-`2`!` Ľķʽ ģ a`-`1`!`, a`-`2`!` DzַͨX`-`1`!`, X`-`2`!` ǷDzַͨ㴦ڍ ǵȴ״̬ s`+`0`!``-`p`!` £ͨ a`-`1`!`, a`-`2`!` ϴݣڣ`-`1`!``-`1`!`, `-`2`!`ϴݻַڣ֣ʱɱ𣬲 ͨ b`-`1`!` ϲַa`-`1`!` a`-`2`!` ֵĺͣͨ X`-`02`!` Ͻ ͨX`-`2`!` еעX`-`2`!` еѸֵıҲδ ֵıĵַV`-`2`!`ڴͬʱдͨ u=value(a`-`1`!`)+ value(a`-`2`!`) ֵдַ address(u) ȥͬ㴦ڷǵȴ״̬£ a`-`1`!` a`-`2`!` ϴݹһδֵıĵַX`-`1`!` X`-`2`!` ݹѸֵδֵıʱҲɵ𣬵󣬽 a`-`1`!`, a`-`2`!`, X`-`1`!`, X`-`2`!` еԭ״̬ s`+`0`!``-`p`!` ڲĴ RegisterУ ״̬ q`-`waitp`!` ʱܾͨеݡڵȴ״̬£ͨ ͨԭ a`-`1`!`, a`-`2`!` δֵıһֵϱ öͨ R Ӵ洢жȡֵͨ b`-`1`!` ϲ ȴ״̬֮ǰͨ a`-`1`!` a`-`2`!` ϱĺͣͬʱֵ address(u) У ͨ X`-`02`!` Ͻԭ X`-`2`!` ֵȥ ƣеΪ˱֤۽𾭹мȴ״̬񣬍 b`-`1`!` Ķ a`-`1`!` a`-`2`!` ϱĺͣ X`-`02`!` X`-`2`!` еč .˵ǽҪģͿԱ죱̸Ĵͳģ͍ ĵڶ㲻㣺ȴDzַ±ͨһ˵ģͬԿˍ ͳģ͵ĵĵ㲻㣺ľԡڴͳģ͵ĵһ㲻 ģȻǿ˷˵ġӶǿΪǽҪģһֱȽύ ģ͡ . ͼһĹ涨 a`-`1`!` a`-`2`!` a`-`3`!` R ةةة W Щ b `@M` ͼ. Ӧ If f(a`-`1`!`) then f(a`-`2`!`) else f(a`-`3`!`) Ľ p `@A` ʽ涨£ I`-`p`!`={ a`-`1`!`, a`-`2`!`, a`-`3`!` } R`-`p`!`={ R } W`-`p`!`={ W } O`-`p`!`={ b } S`-`p`!`={ s`+`0`!``-`p`!`, q`-`waitp`!`, s`-`1`!`, s`-`2`!` } s`+`0`!``-`p`!` Ϊʼ״̬q`-`waitp`!` Ϊȴ״̬ Register={ } G`-`p`!`=G`-`1`!`G`-`2`!`G`-`3`!`У G`-`1`!`={| `-`in`!`=[(a`-`1`!`, x), (a`-`2`!`,), (a`-`3`!`,)],`-`out`!`=[(b,)], `-`w`!`=[], xV`-`1`!`, f`-`1`!`(x)(i=1), ( f`-`1`!`(x))(i=2)}; G`-`2`!`={| `-`in`!`=[(a`-`1`!`,), (a`-`2`!`, x), (a`-`3`!`,)], `-`out`!`=[(b, y)], `-`w`!`=[(address(y), y)], x,yV`-`1`!` }; G`-`3`!`={| `-`in`!`=[(a`-`1`!`,), (a`-`2`!`,), (a`-`3`!`, x)], `-`out`!`=[(b, y)],`-`w`!`=[(address(y), y)], x,yV`-`1`!` }; ƣ={ } ֱϽýķʽִIf f`-`1`!`(a`-`1`!`) then f`-`2`!`(a`-`2`!`) else f`-`3`!`(a`-`3`!`)һ f`-`1`!`(a`-`1`!`) ֵ f`-`1`!`(a`-`1`!`) Ϊ棬״̬ s`-`1`!` ״̬ s`-`2`!`ڶ״̬Ϊ s`-`1`!` s`-`2`!` Ӧִ f`-`2`!`(a`-`2`!`) f`-`3`!`(a`-`3`!`) ڱڵǸͼĶ壺 売. ǽͬͨļϣСģ͍ ãģƣ`-`N`!` εһ涨ãģƣ`-`N`!` һʮһԪ飺I`-`N`!`, O`-`N`!`, R`-`N`!`, W`-`N`!`, Register`-`N`!`, `-`N`!`,`+`0`!``-`N`!`, G`-`N`!`, ƣ`-`N`!`, Bus`-`N`!`, Memo`-`N`!` I`-`N`!`=(`-`p P`!`I`-`p`!`)\(`-`p P`!`O`-`p`!`) N ͨ; O`-`N`!`=(`-`p P`!`O`-`p`!`)\(`-`p P`!`I`-`p`!`) N ͨ; R`-`N`!`=`-`p P`!`R`-`p`!`; W`-`N`!`=`-`p P`!`W`-`p`!`; Register`-`N`!`=`-`p P`!`Register`-`p`!`; ƣ`-`N`!`=`-`p P`!`ƣ`-`p`!` Memo`-`N`!` Ǵ洢; Bus`-`N`!` ǵַ, R`-`N`!`, W`-`N`!` еĶдͨ洢 Memo`-`N`!`; `-`N`!` Ĺμ, PCRegister`-`N`!`Memo`-`N`!` ϵӳҵļϡֱ Ͻ `-`N`!` еһΦңθ pP(p)Ϊ ĵǰ״̬ θͨ cC (c) Ϊͨ ϵĵǰݶУθĴ Register`-`p`!` Register`-`N`!`(Register`-`p`!`)ΪüĴеĵǰֵ;θ vMemo`-`N`!`,(v)Ϊ Ԫ v еĵǰֵ; `+`0`!``-`N`!` ʡ`-`N`!`,ÿ p ӳΪ s`+`0`!``-`p`!`, C,Register,Memo ӳΪֵ; G`-`N`!` DZǨ,: 1. ڲǨӣҡ',ڽ p ĵ: <1>. ; <2>. ; <3>. ʹæӣ ҡ ' p һε,ʽ˵(עֻ<1>. ˵,),: (p)=s,'(p)=s'; (p')='(p'), If pp'; £(in`-`i`!`)='(in`-`i`!`)x`-`i`!`, If`-`in`!`=[(in`-`1`!`, x`-`1`!`), ,(in`-`n`!`, x`-`n`!`)] and in`-`i`!`I`-`p`!`; '(out`-`i`!`)=y`-`i`!`(out`-`i`!`), If`-`out`!`=[(out`-`1`!`, y`-`1`!`), , (out`-`m`!`, y`-`m`!`)], and out`-`i`!`O`-`p`!`; (c)='(c), If not cI`-`p`!`O`-`p`!`; ã(Register`-`p`!` )='(Register`-`p`!` ) If pP; ģ'(v`-`i`!`)=z`-`i`!`, If (v`-`i`!`, z`-`i`!`)ʦ`-`w`!`; v`-`i`!`, v`-`j`!`Memo`-`N`!` '(v`-`j`!`)=(v`-`j`!`), If z(v`-`j`!`, z)ʦ`-`w`!`. . Ǩӣҡ' in`-`i`!`I`-`N`!`, xV`-`1`!` ʹ '(in`-`i`!`)=x(in`-`i`!`), and '(in`-`j`!`)=(in`-`j`!`) for ij. . Ǩӣҡ' out`-`j`!`O`-`N`!`, yV`-`1`!`, ʹ (out`-`i`!`)='(out`-`i`!`)y and (out`-`j`!`)='(out`-`j`!`) for ij. ʽĶ壬Ǻ׶ģͣãģƣ`-`N`!` һƍ 㣺 `-`N`!``+`0`!``-`1`!``-`2`!` ͨһǻ֣ᷢȻǵģж˴洢 Memo ַ Busȴ״̬ڲĴȫֱδֵıɍ ʵȹܣЩ⹦ֻ𵽳㷨ľ̬ԣټ ٶȵáҲ˵Щƹ﷨ϵģϣӦ봫ͳģ ơȻÿֵͨ˳ÿͨύ ֵ˳֮Թϵͳģ͵ĸ؍ Ҫ޸ľӦǵģͣãģƣͣͨڴͳģиЍ ģͣãģƣȻУ֤Щһַ߳ζč £ڴȥ `@p` 죳 ãģƣ͵Ӧ`@A` ڽģͣãģƣȥʵ⣬Ҳ˵ڵĿڍ ۣζһ㷨ģͣãģƣȥѰ̬ԡ ڵĽṹģ.ԣģǣ̣.ܣգ ͣͣã .ܺĽգ ͣͣãͲл;.܍ ããģƣͽգ ͣͣãͲлķܶһ ãģƣͽⲢл . ͼԣģǣ ģǣ R.Jagannathan ˵Сڣӣңɼѧʵҿč һڹվͼ[JD89]ıʽıʾԿǣԍ ͼԵıʵҲʽִЍ ϵͳɶԣģǣ̽нִ͡УЧãڱģǣ̍ģͣãģƣ͡ԱĵģǣԽʵ޸ģ һڣӣңʵҵִϵͳУڣģǣ̵ϸɲοЍ ס . ģͣգ ͣͣã .Ǻ ΪһϣΪȻ<>`-`N`!`ʣ`+`*`!` ||N ʾ`-`1`!``-`2`!``-`3`!``-`n`!``-`i`!`ʣ ʾ`-`1`!``-`2`!``-`3`!``-`n`!` ʱ涨 ţ֣ ʾ`-`1`!``-`2`!``-`3`!``-`n`!` ʱ涨ţ֣ ʾ`-`1`!``-`2`!``-`3`!``-`n`!` ʱ涨ţ֣ ʱ涨`-`1`!` .ģͣͣͣã ڣͣͣã͵ϸμֻҪ 壺һͣͣã һԪ飺 ףѣ`-`h`!`ƣУ <1>. һĸ <2>. `+`*`!` Ϊʼַ <3>. Ϊ״̬ `-`h`!` Ϊͣ״̬ <4>. ƣ`-`1`!`ѣ`-`h`!``-`2`!`ѣ `-`1`!` <'ȣ>`-`N`!``-`2`!` <ȣ'ȣ֡ȣ'> `-`N`!`֣`-`1`!``-`2`!` `-`n`!`'ʣ֣'ʣ `-`1`!`еԪ `-`1`!``-`1`!``-`2`!``-`2`!``-`m`!``-`m`!``-`m+1`!`2m+1Nƣ񣩣`-`1`!``-`1`!` 򣨦`-`1`!``-`1`!`a`-`1`!`,a`-`2`!`,,a`-`m`!`,qҪڦг֣ ڦ`-`1`!`г֡ <5>. Ϊʽ̼ `-`0`!` `-`1`!` `-`t`!` ʵеһ: `-`i`!` `-`i+1`!` ʣȣ'`+`*`!` =a`-`1`!`a`-`2`!`a`-`i `!`a`-`i `!`a`-`i `!`a`-`n`!` v`-`1`!`=a`-`1`!`a`-`2`!`a`-`i-1`!`; v`-`2`!`=a`-`i+1`!`a`-`i-1`!`; ; v`-`m`!`=a`-`i +1`!`a`-`i -1`!`;v`-`m+1`!`=a a`-`n`!`. ǵõ =v`-`1`!`a`-`i`!`v`-`2`!`v`-`m`!`a`-`i`!` v`-`m+1`!`, ãƵã( ,q`-`i`!`)=( ,q'); еv`-`i`!`ַرæ ;q'=q`-`i+1`!` ⻹Ҫq`-`0`!`Ϊʼ״̬,q`-`t`!`Q`-`h`!` ȥͷǣ׵Ԫء һ¿ɷ֣գ ͣͣãͻ 壺һͣͣã ͳΪһ¿ɷֵģUniformly Separable ָ ƣ`-`1`!``-`2`!` д(v`-`1`!`a`-`1`!`v`-`2`!`a`-`2`!`v`-`m`!`a`-`m`!`v`-`m+1`!`,q)(,q'); <1>. ijֻڣ <2>. 'ֻڣ <3>. (VV')еĸĸڦгԼڦеľλֻڣ <4>. A' ĸڦгֵλֻڣ <5>. (AA')ĸĸڦa`-`1`!`,a`-`2`!`,,a`-`m`!`,q . һ¿ɷ֣գ ͣͣã͵IJл ڣHu90˶һգ ͣͣãͿɲлij ˴Ӵееľת㷨ͼ 봮 US MMCM 㷨㷨 ת㷨ȱԱ `@M` ͼ. ֮ `@A` [1] 㷨ݽṹʽʾ LISP ԱдԶת P: `-`0`!``-`1`!` `-`n`!` US MMCM һ̣[1]еԶת̣и õ I`-`1`!`,I`-`2`!`, , I`-`l`!`, 㣺 <1>. I`-`i`!`={1*, 2*, ,n*}; <2>. I`-`i`!`I`-`j`!`={ } for ij; <3>. If I`-`i`!`={n`-`1`!`*, n`-`2`!`*, , n`-`k`!`*}, Then P , n`-`1`!`*, , n`-`k`!`* ǿɲִеġ ģͣãģƣͿʡȥHu90еת㷨һֱ֪ һ񣨻 US MMCM ̣Աé CDFM ģͩ `@M` ͼ. ãģƣ ģù`@A` գ ͣͣã̵±Ʋﵽת㷨ٱ ЧͼȻãģƣͲڣգ ͣͣãͻһĹ ǿʵõġ . Sun ϵͳµĹվִ US MMCM 㷨 N 룬͵ǣ P: `-`0`!``-`1`!` `-`n`!` 裱̣ÿһ *`-`i-1`!``-`i`!`һãģƣͽ i`-`M`!`磬 *`-`i-1`!` `-`i`!`ʽ a`-`1`!`X`-`1`!`a`-`2`!`X`-`2`!`b`-`1`!`X`-`2`!` ʱ a`-`1`!`a`-`2`!` DzַX`-`1`!`X`-`2`!` ǷDzַb`-`1`!` ַÍ ͼ.еʽ涨䵱òʽ i* ģãģƣͽ i`-`M`!` 裲裱õĽ㼰ǵĸͨģǣ 磬ڶӦڲʽ a`-`1`!`X`-`1`!`a`-`2`!`X`-`2`!`B`-`1`!`X`-`2`!` ģãģƣͽ㼰.е ʽ涨ͼģǣͼijɷΪ <1>. Ͷ壻 <2>. <3>. 裳裲õĸͼķʽ ͨõͼеģǣԿڣӣңʵ Sun OS СϵͳִУΪǡʽִ еķʽһͨ [1] ж̷࣬Ȼдִеķʽ һǿ˵ģͣãģƣͿʡȥ [Hu90] ת 裬˱ԱĹڱĵĽβǸһãģƣÍ ͨĿܲ裺 . Էֽ T`-`1`!`, ,T`-`k`!` . ÿ T`-`i`!`ַ룬Dzַ룬² Ȼ T`-`i`!` Ӧģãģƣͽ㣻 . 涨롢ͨģǣ . ۺϵеĸγԵģǣԣ . ϻԣγ`@M` ںĹ󸱽ںͺоԱָ ɵģڴ˱ʾĵĸл`@A` node_i`-`M`!`_Definition (in`-`1`!`, in`-`2`!`, in`-`3`!`, in`-`4`!`, &out`-`1`!`, &out`-`2`!`, R, W); typedef char operating; typedef char string[100]; typedef string reserved; typedef char newborn; typedef rw_channel real; genedge operating in`-`1`!`, in`-`2`!`; genedge newborn out`-`1`!`; genedge reserved in`-`2`!`, in`-`4`!`, out`-`2`!`; genedge rw_channel R, W; { /* in`-`1`!`, in`-`2`!`, in`-`3`!`, in`-`4`!` are the incomming edge of node i`-`M`!` */ /* and out`-`1`!`, out`-`2`!` are the outgoing edge of node i`-`M`!` */ /* R, W are the Read and Write edge of this node resp. */ /* in the following for each edge specify it's type */ /* specification */ edge TYPE edge_name; edge TYPE edge_name; /* the following is the function description of this node*/ /* i.e. the S`-`p`!`, s`+`0`!``-`p`!`, q`-`waitp`!`, G`-`p`!`, Register`-`p`!` and ƣ */ /* can be defined here */ function_description_of_this_node (p1, p2, p3, p4, &r`-`1`!`, &r`-`2`!`, Read, Write); { } } `@M` ͼ8. i`-`M`!` DGL `@A` /* typedefpart */ the definition of all types indicated in each node and edge can be put here /* edges part */ the definition of all edges will be put here /* nodes part */ the definition of all nodes will be put here /* the main part */ main( ) { node_i`-`1`!`_definition; node_i`-`2`!`_definition; node_i`-`n`!`_definition; } `@M` ͼ9. Ӧ US MMCM DGL `@A` `@p`ο:`@A` [1] һӴ գ ͣͣã лݽṹ㷨,1990. () [2] (Petri) ѧ(ѽܷ) [3] ֵݹ麯, ѧԺѧ, vol.2,1979, pp8-20. [Ag86] G.Agha. Actors: A Model of Concurrent Computation in Distributed Systems. MIT Press,Cambridge,Mass., 1986. [Ag89] G.Agha. Supporting Multiparadigm Programming on Actor Architec- tures,in E.Odijk M.Rem and J.-C.Syre (Eds.),PARLE'89, LNCS 366. pp.1-20, 1989. [AN90] Avind and Nikhil,R.S.,"Executing a Program on the MIT Tagged- Token Dataflow Architecture",IEEE Trans. on Comput.,Vol.39,No.3, pp300-318,March 1990. [BA81] J.D.Brock and W.B.Ackerman. Scenarios: a model of non-determinate computation. In Diaz and Ramos(Eds.), Formalization of Programing Concepts, LNCS 107,pp.252-259, Springer Verlag, 1981. [BP90] M.Beck and K.Pingali. From control flow to data flow,In D.A.Padua (Ed.), Proc. 1990 ICPP,Vol Software,pp53-60, The Pennsylvania State University Press,1990. [Br88] M.Broy. Nondeterministic data flow programs: how to avoid the merge anomaly. Science of Computer Programing, 10:65-85,1988. [GJ89] Gluck-hiltrop,E.,Johnk,M.,Schurfeld,U.. The stollmann Data Flow Machine, in E.Odijk M.Rem and J.-C.Syre(Eds.) PARLE'89, LNCS 365 pp.216-234. [Hu88] Hu Guoding(). On the Mathematical Model of Computing Ma- chine, J. of Computer Sci. and Technology,Vol.3,No.4,1988. [Hu90] Hu Guoding(). Parallel Computation Simulating Sequential Computation,1990.(to appear). [IE82] IEEE Computer Vol.15, No.2, 1982. [JD89] R.Jagannathan, A.R.Downing, W.T.Zaumen,and R.K.S.Lee. Dataflow- Based Methodology for Coarse-Grain Multiprocessing on a Network of Workstations, in E.C.Plachy, P.M.Kogge(Eds.), Proc.1989 ICPP, pp.209-216. [JK89] B.Jonsson, J.N.Kok. Comparing Two Fully Abstract Dataflow Models, in E.Odijk M.Rem and J.-C.Syre(Eds.), PARLE'89, LNCS 366 pp.216- 234. [KP85] R.M.Keller and P.Panangaden. Semantics of networks containing in- determinate operators. In Brookes,Roscoe,and Winskel(Eds.), Semi- nar on Concurrency 1984, LNCS 197,pp.449-496,1985. [Pa83] D.Park. The "fairness" problem and nondeterministic computing net- works. In de Bakker and van Leeuwen(Eds.), Foundations of Computer Science , Part 2, pp.133-161, Amsterdam, 1983. Mathematics Center Tracts 159. [Sh85] Sharp,S.A. Data Flow Computing, ELLIS HORWOOD LIMITED,1985. [SK86] Sargeant,J. and Kirkham,C.C., "Stored Data Structures on the Manchester dataflow machine" Proc. 13th Annu. Sympo. Comput. Architecture. pp.235-242, 1986. [WT90] H.Wu and L.-E.Thorelli. Extending data flow Principles for mul- tiprocessing, In D.A.Padua(Ed.), Proc.1990 ICPP,Vol Software, pp53-60, The Pennsylvania State University Press, 1990 [Xu89] Xu Shuruen(). Petri Net-like Languages(to appear)