1995

YyÐùêÑÃí (JSPP'95) _n
PIE64 934;=AFI?GJD<N25BHFIL@{ CFI?G7OFI?G; P6:GQ8KR:>E7MA {TX WY Z[ U` ]\ C^
Sabc Vc_», Ãìý*-,VÚDÖ)|9,¨, Ã B¨Z|9 ,.
eg
0, ²Äycï0 ± ,, ¸oxsAÄsAÍ90ñ1{8, Ï z743, cÅ(½¸6
! U¥ÍDÜ0 Ã+9ý, hz70'Ù36 60ð÷7,0, hz70eMv âÖù0EvÆ yF0|& ,. Ö£0y¶ , ÍùâÂô),y»ë,0ÉTú,.
ÅùÑù PIE64 ¨o;8>, 1) i5åøÔØÏ, C ²»l~ ,»\0P*-, 2) y»0 ÖÁ, 6)üÄycïþûÍ§wÄûªÆ, qR!'Äû<¸½>  0P,&, ú*ÿ9&Ï (xsAï)
0P*-, 3) y»0xûªÆ, Ï y ! (ÄsAï) U¥ÍDÜ0ï*8,),³JN9. ¿¨0P*-,60PX8. ÃsA­879ÍDÜ0+9ý,, EvÆ yF0|& ,. 6-, Ey»0§w
Äûq-8û,, Ö¹J0,
Abstract,Fûü]ÖÂý]ûû,.
We propose hybrid-grain parallel processing wherey»0§wÄ3, åøÔØÏ0?L8û,, q]3! y0Í Ãheavily-loaded situation and lightly-loaded situaú,. 0 fork 8y»0Ä&', tion are explicitly distinguished in static optimiza0 Ã ,åøÔØÏ3, ÆDáæØÜ0)<tion, and two-version codes are switched dynami,4ú+, q0û Ã0½0cally. An evaluation of the method in PIE64 shows(1) comparable single-processer performance with
û. ¨óq ` Q¤ú+, «the C language, (2) near-linear parallel speedup§wy»0P7-û, ,.
under high concurrency, comparing even with se0, y»0q-8û,, Ï yquential processing, and (3) the same parallel0Í Ã,. öråøÔØÏ00Ñ
speedup under low concurrency as the maximum,&, 0 fork -v Ã-7-, y7-,. ÍùâÂôþ4,Í9, Ö
speedup by ne-grain parallel processing.
)0[6ú,@¡0q98, y»¿¨0ç7
ÊõÙÁÇöâÒ0l« ,6
1
mhnk
0ªð,.
½ûy0 ± ,, sAw(Ò ÖÁ|& ,vÆ y),Í ºÌÑñDõùËi(, Í90 ¹, y¶ÅùÑù PIE64[2] ¨, Ï y,0, Í 0÷&,í+û. m ïÍìØÙÁØÜ×óÂÒ7²» Fleng[11]ûý, y»ÄûåøËôíB y»0ò 0ïû (8, o;0Ã.
º8 0!3803, y»xûåøË ÖÁÀ¼'8w+ú,: 2 , !ôí, y»x80g4 0Ïÿ380 yÏ yP0­!, |&û [7, 9, 12, 13]. 8ÿ8, åøËôíSÑ ,y fR ,. 3 , xsAÄsA, :z7-,­ý(Í Ã88, Í9´0)ü,Optimal granularity control by hybrid-grain parallel
,ÿ0z»9,. 4 , PIE64  Flengexecution in PIE64 { ne grain vs. coarse grain;ûÞ8, 5  PIE64 þ4,Í ºdistinction and fusion of two heterogeneous worlds { byYasuo HIDAKA, Hanpei KOIKE, and Hidehiko TANAKA¹, 6 »\o;û­!,. $, 7 (Faculty of Engineering, The University of Tokyo).
[øû­!,.
E-mail: fhidaka,koike,tanakag@mtl.t.u-tokyo.ac.jp

£

q
£

n 1: qN¥yfR.
! yÏ y
£ (+ a£)( £ +) a£(twa£)(tw £)q²»
Ï y²»

¬_
q²»
Ã½
2
y»s¬ |||||| 2
ã>
»\¿¨³J hz7wSÉT ÆDáæØÜ=è½/ |||||| y»y > PE¸ 2 n y»y < PE¸ 2 n

vÆ y
(+ a) *) ( +) a( Ã+9ý)Ï y²»ÍDÜÏÂÓ=/t|y ¨ª, PE1 µ©¤»§¾Æ.
v¬Î ¶ÑØ§¾Æ. PE ÅÁÀÚ¸§¾¿¼, PE ÅÙÓ¦ÊÂË±, Ê§¾ÛÖ§¾¿¼ ¡, PE ÅÙ¯²Ø×ÂË° È¡ .
n 2: xsA­8ÄsA­8fRÝáæëâ óáæëâ
xsA­8
ÄsA­8
­ý.û
! y, qtwa£[6y»0xûy»0Äû
0OV8', Äû Ã½ûüô0b
ör
PE
0
0
Ñ
PE 0?Lrß, qåøËôíwS0í+ûûüã>
fork -v Ã fork 8'¸H80ú,. Q, hz7þ4,MwSÉT
jwait queuej 0jwait queuej=0
, ±­åøËôë0N_ÝI0$V8wSÖ FIFO £ FIFO/LIFO ú=0Ãû,0, N_Ý$VìÒ_0T8priority 0è½priority Ü½
3, -0g4)ü3¸N_Ý0$V ,,Í Ã88, Í9´.û
y»0q-8Äû?L0P*-û.
Ïy0]Ö q0]Ö
0, Ï yô,  0auç Ã
°7ç Ã
£[68n± ,6.ÿ*¬_8û,&,øDÇõÙÁªy»ªåøËôíSÑ , y»0í+s¬
Critical path l«ÆDáæØÜx¯
1,6, N_ìÒ),áË0ú$+d6*û6ÃZ0Zl«ÃZ0vl«ú,. 8ÿ8, pdÃ/-,N_IsAwª
ÒÌÑñDõùËªÆDáæØÜ=13, q(! yR(Globalscheduling)(Local scheduling)!½0%ûûüã>0ú,.
` 0è½
Suspend ë,0è½
vÆ y, ¨cô0#%Æ/ú,. /, Ï y²»0¬_8Í=³y»0s¬ ,. 8, §wÄ PE 0?Lrÿú+, 6ÿ* .û0¾9,.
ûy»0P*-û,, £[6),Í8þû, 0 fork -ör
90 ßÎ+V-q%Äû Ã PExsA­)vy
Ã7-,. µ, Ã7½0A¼8, qR!'§wÄû<¸½  wait queue u7"#«
0 ú+, 
>0P,60á . $, y»0xû, a Ö FIFO £, priority 04'½>û£]3Ï y0Ãû, ?L0¿¨ xsA­8þ4,Í Ã88, Ï y.
7 =\³+. ¿¨0á .
0]Öú+, FIFO £)+ uç Ãþ, N|&fR0n 1 .
,. ÍùâÂöÍ9, øDÇõÙÁ)+y»0ª8, q9)0[6ú,twèFõßkopDjqúil÷d
&,!1ú,. @8, õïDÛ ÃÍÒÛ0Ö, ð"åøÔØÏ (PE) ¸R!§w Â8, fork 80vy Ã7-,
Äûy»0P*-û,EÄsA­8F, &6 :z8, critical path u0Íl,)ü globalxûy»8ÿP*-ûûExsA­8F, scheduling ) ÃZ0vl« !1ú)ü­ý0,+, >, Í Ã88( ,. $, PE S local scheduling *Ú3, )Í9´0)ü,,ÿ09, (n 2).
0[65sAw0ªðú,. ör PEÍ'Ö.û, ör PE 00Ñ ,ÿ 0ê ,6û&, ` 0è½ú+,
n111

y111

2

3

vs

Inference Unit
UNIREDLMEM

NIPMulti-Stage
Interconnection
NetworkMP

Hostµ 1: y¶ÅùÑù PIE64. 64 <¶òÝØÛ 2 9J&·Æà0. MsAw`\0, ëÐù 5sA­8`n0í+=\.

I/O

UNIRED - Unifier/Reducer
NIP - Network Interface Processo
MP - Management Processor
LMEM - Local Memoryµ 2: ¶òÝØÛÀ¼. 0jü UNIRED ,
NUMA 7úèîïõ0|ù8, ÏÂÊö×ÍùÙÊÒÛ+9ý)+w¯÷ÂÙùÐ03z ,.
4.1

PIE64

lü5þ2ÿ13&·Æà [16] , sAÍ¥ IU 0M?8
sAw0Ãü, MsAw`\0jýû,.
$6`\0ôï8, N IU ëÐù 5sAÏÒèùÜQº Ã'ú$+ã>û.
0, ÄsA­8 PE 0?Lr, 0 ­80í+p,6'¬ó,. /, N IU 0
fork 8' wait queue V¸H8,. queue ±Ç8sAo&·ÆàSfR7-, Í¥o0 Ã70ú+, FIFO ( LIFO, priority N IU äÁDÜáØÊ7-,&, 6Í¥sAo
OV, îC local scheduling 0=\ú,. 0N IU 0øDÇö6ofR -û.
ÄsA­8þ4,Í Ã88, q0] IU[6] , 0jü UNIRED (Uni er/Reducer),Öú+, ÒÖØÊ0ïûB©y»0Mòº Y0jü MP (Management Processor), w¯BN=\, °7ç Ãú,. ÍùâÂöÍ9 _0jü NIP (Network Interface Processor) ¥, øDÇõÙÁ0ª !1ú,. fork 0¯* åøÔØÏIÿ*À¼7-, (µ 2).
8q9 ,6)+, øDÇõÙÁ0¿¨ , UNIRED[15] , åøËôí0 Ã ,îÂùå
ú, fork (N_ÆDáæØÜ0Ó¯7-, Ã øÔØÏú,. 0e RISC 7ÝÔØÛ
ZZl«7-,. sAw)+'N PE S Fleng 8¡VÝ0, 2 IU 6 ,
 local scheduling 0ªð, ÏÒèùÜ1, îïõ¦Ý0 NIP ÍëùÜM|W ,4Hg !1ú,. $, ` ;oû. NUMA ÀDÉÙÊ×ð0. $, 4 ÔØÛ÷6)ü, ÄsA­8xsA­8, åøË ÑÒÖä¿Âö Program Counter(PC) 0ÏÂÊôíÍ9´0 180 ,,. 6&Öø ö×+9ý,ëö×ÍùÙÊÒÛ)+, w
, ! ïDÜÏ ïDÜU¥ÍDÜ0 ¯÷ÂÙùÐ03z ,. 0, Ã=\ÍùÙÊï*8, --,,´Í98, Ãs ÒÛ%0âÂåôÂù/V8, y»q-½x80Õûû,.
A­8) -*0+9ý,0,.
, sAw, ÒÌÑñDõùË0& ,(¨êÂùÛ, ÄsA­8ÿ*sA0x88 YMP
+9ýú,. ! ïDÜy» 0jû, cï RISC ú, SPARC ,
0ÒÖØÊ8q Ã ,ªÆ, xsA­8 ä¿DíÃÄÀú,yYÇDÞö [7] 'q Ã0/3?L0x8 ,&, 6 )À¼7-,. þ, H  UNIRED 0 
Z7 ,ëzú0, MP 0éÛöÞØ
ÒÖØÊÿ*y»0s¬84-*û.
Ê&, ±Ñ (, Y0t0
UNIRED-8, MP sA0¯*8û,.
ëâöäý404Ö, y¶ÅùÑù PIE64[2] ¨, ÍìØóáæëâôàíï
ÙÁØÜ×óÂÒ7²» Fleng[11] 0ïû (8.
PIE64 , 64 <¶òÝØÛ (IU: Inference Unit)
Fleng[11] Ï y¿1²», ÍìØ´-,ð"åøÔØÏ, 2 9J&·Æàÿ ÙÁØÜ×óÂÒ7²», y7²»0¥ú*À¼7-, MIMD 7y `ú, (µ 1).
,. N¥²», GHC[18], KL1[19] 0ú,.
o

4

PIE64

4.2

Fleng

User

UNIREDTop Goal

Any
Goal

MP
reduceSTART

Goal Scheduling...

dispatch

Activate
Wait for Value
SuspendNotifyHead
Unification

Commitendreduceload args.

ActiveBody
Unification Reductionµ 3: Fleng  ÃïÚö.

Entry Point

Body
Goals

compiledpredicatedequeueschedulersuspendsuspendprocedure

no-bodyclausehead
unification

queue/stackgoal frame

clause withbody
built-inpredicatebuilt-inpredicategoal frameenqueue

END
fork goalþ4, i(ÎDö´-,åøËôíze¦Æ8ìý*-,. åøË
NIPôí Ã, (1) $ ÉñDÿ*ÎDö0¢+¬8,(2) ÎD öË} (head t) 0 unify =\z e0?8, (3) ze4} (éÚÁDt) #
Network%È%­» (active unify I) 0 Ã8, (4) éÚÁDtÎDö reduce 8ÉñDâ , ûü%Ò
5+~8ú, (µ 3).
µ 4: Ï þ4,-.
ÎDö Ã£ºæ3, y Ã8
'À/û0, æØÜòÝä¿ÂÛze|¸ ÿ+ ûûý, q7²»£/1´¬8o0mðú,, ÎDöÏÒèùÜ ,. Ï
, '8)üÆDáæØÜ0ú,:
ÒèùÜ8ÎDö, 2ÎDöéÚÁDtþ R!,û|¸03597-,, ÀÊÙÁçÂÛ7-Ì  £6/81´¬82¸÷ÑÒÖ8ú,, ÎDö fork îïõ8,.
ÉñDâ7-,. þ, |¸i0;Vú+,  £/1´¬8
, ³£/1Sw^ÝváØÊÛôØÊ0Ã/û.
´68, ÎDö fork , GF ¨­»cÅO[ / R%¬8, ZÑðùå,.
4.3
hlóáæì8koq9Þ £/1´¬8mðû, ÎDöÉñDenqueue/dequeue  (MP ¨) 0mð,.
åøËôí8ìý*-ze¦Æ, ­»0
, Øk´¬8, 2¸0÷ÑÒÖ¨ï×$&ÍùâÂö7-,. 6­», q7£/1²»þ4,£/1([¸7²»þ4,[ *8 EP vÑðùå ,&, q7²»£¸&H8, ÎDö, £/1´¬8([¸´¬ /1´¬8ÍÒÛ"#N9ú,. $, headuni cation , 2¸7(o),w ^ú
8&H ,.
+¨óÏ  (þ4,-0, µ , q7²»¬w^&H ,. ÍÒÛ, ÏÒèùÜ0¾94-¬w^N} ú
4 . UNIRED ÚÁÒâØ×öD×ù2¸+
0÷ÑÒÖøDÜ8, ÍùâÂö7-MH­» , fork (Øk´¬8)+'0eÿ+¥7û.
ÅùÛõêÂùÛ (EP) Ñðùå ,. Head uni- þ, µ 4§7-û,0, ÏÒèùÜ, ÷ÑÒÖ¨2¸0 GF :g8, ÏÒèùÜ
cation ¼¼8ze0?7-,, éÚÁDt#%È%­»0 Ã, éÚÁDÎDö000¤û ÍëùÜ0 NIP _Ã8, MP  endreduce 0_  fork 8, Í¸, ,0ÎDö0Øk´ Ã8, MHÍùÙÊÒÛ0y7 ,.
¬8 (tail call: Ìa³*û) )+ Ã ,. 6
0, éÚÁÎDöûze0?7-,ÿ, 5 PIE64 kfgqòåáæøîl9ÞÏÒèùÜ0¾9,$5+~ .
ÎDö fork , ãDåîïõ¨­»cÅ( 5.1 éñáæì8l9Þ
2¸0¢1È1ÎDöä÷Dí (GF) 0Ò¼8, vÆ þ4,-0µ 5 . N
NIP (W* IU/ z IU  Ã ,), $ MP­»Ï ïDÜ! ïDÜU¥ÍD(øDÇö IU  Ã ,) 5,. 6 fork Ü0, -- EP 0. Ï ïDÜ,
Flenglocal fork

newloadfork goal

prepare args.

tail call

Entry Point

remote fork

UNIRED
break

compulsory fork
in coarse-grain mode

IU0

load flagcoarse EPcoarse-grain modefine-grain modeload-drop
detection

reduceSTART

blank period : IU idle

TIME

MP

fork tail call enqueuedequeue

call return

IU1

flag checkIU2
nodispatchcoarse EP

endreduce
dispatchcoarse EP

fine EPsuspendhead or end
unificationsuspendhead or end
unification

dequeuequeue/stackIU3

thresholdlevelheavily
loaded?

+
-

yes

IU4
start

IU5
IU6
IU7

fork goal

call goal

fork goal

local fork
remote fork

coarse EP
tail callcoarse EP

NIP

tail callcoarse EP

local load level

call goalend orsuspendsuspendand returnµ 6: vÆ  5 ÃÂîDÑ.

global load level

RET

newloadenqueueFREEfine EP

FC
RET

END

END

JUST

Networkcoarse-grain modefine-grain mode

µ 5: vÆ þ4,-.

ERER

automatic loadbalancing / propagation

RELEASE! SX&EQ

NG
&L

NG
&L
EQ

SX&EQ

! SX
&! EQ

LOW
SUSTAIN¨óNî fork Øk´¬8), Ã0Ãû,! ïDÜ, fork ;/+ call ),qÃ0Ãü. $, 5 Ãîµ 6)ü+, B, IU Z(N9 UNIRED 
HIGHÍùÙÊÒÛZ, UïDÜ0ÊÑ ,.
sA­8`zÆDáæØÜ0òý,&, `zÚÁÒâØ×öD×ù%Ãû, '¸, ÍùÙÊÒÛy ,$N9ïDÜ Ã ,. @8, ! ïDÜy»0ÒÖØÊ8u µ 7: ÒÌÑñDô­8-. 4å1-!Zq Ã0Ãü&, xsA­8'! ïDÜ0/4û,ÍùÙÊÒÛ (sticky context) ïDÜ Ã0/4,?L0x8 ,. 6  break(0¥S+È%) 0ÿ4, üº fork 7 ,.
&, ! ïDÜ ÃrxsA­8â,, MP
n 3: ÒÌÑñDô­8.
)+ break(0¥S+È%) 0ÿÿ, (¸­).
UNIRED ÒÉ³¥# ÒÉ! ïDÜþ4, call , 2¸ (÷ÑÒÖ¨) Ã´contextxÜvÜ~â+ÀÜ÷Ò (ÒÖØÊ¨) 0ï*8 EP i
FREE


×
Í
4, fork tw'0Ã/û. ´
JUST
·­

×
Í
¬8+q7²»£/1´¬8"#N9
LOW·­  × Í
ú+, £/17²»NîÒÖØÊä÷Dí (SF)HIGH·­  Ê Í / ®
SUSTAIN·­  × Í / ®
Xû00 ,. SF , æØÜt Ã¸ (zeRELEASE·­  × Í / ®
0Pz8) P8, Øk´¬8vK,. ´¬7-+, æØÜt2¸0×ÄØÊ ,0, ÏÒèùÜ8û³+ ÍÒÛ¥7û. û1 , HIGH ­8þûîïõ¨sAäôË0ÄsA­8 ,. UNIRED 6sAäôË0
5.2òåáæøîl9Þ
1 Ä 7Õ H, L , "«w|uz}Å + ÒÉ³xÜ Å¢MP ¨ÒÌÑñD ôn 3 6 ­ 8 0,Ð IU ¥#Ô¯Ç Ë¹½, sÜ~{u¡ Ì
ÉñD­879, µ 7 ­8-0Ã À¥#Ô¢Ïºw|uz}Å£Ù ! .
NG
&H

NG
&H

H

EQ

H

L

H : High Load
L : Low Load

ER : End Reduce
NG : New Goal

FC : Full Contexts
EQ : Empty Queue
SX : Sticky Contexts

: head (done)
current: head (not done): body (done)

C Lang. (SS1)
cc -O2

1.10x108

gcc -O2

1.01x108

gcc -O2 -mflat

9.78x107: body (not done): call: tail call(a)üº fork 8ûªÆ B}.

break

: executed
before break: executed
after break: trapped jump
instruction: compulsory
forked goal)+, üº fork 7-,ÎDö.
µ 8: ! ïDÜþ4,sAx8y»s¬.
(b) breakHybrid (1IU,1ctx.)

1.24x108

Fine (1IU,1ctx.)
Hybrid (1IU,4ctx.)
Fine (1IU,4ctx.)
Hybrid (64IU,4ctx.)
Fine (64IU,4ctx.)

2.21x1088.20x107
1.18x1081.06x1081.40x1080.0x100 5.0x107 1.0x108 1.5x108 2.0x108 2.5x108

Number of Total Execution Cyclesµ 9: N),' ÃÏÂÊö¸fR. vÆ, C ²»l~ ,q Ã½08, ¨óÏ )+'½0û.

'Ö£07ï1,.ü. $, àDÜÃÄÀ, ËøDáöúèÀÜ÷Ò4Z0Ñ, þ, Ï / ! ïDÜ0? ,.
Ï y Ã(MsAw&q=
HIGH ­8sA0x8 ,, îïõ¨sAäÂý*-,0, MsAw(sA­8¬, ÕôË0xsA­8â8, SUSTAIN, RELEASE ­ äÛÃÄÀ';ï=\ú.ü.
8- ,0, ! ïDÜ0vy7 ,68û. SUSTAIN , MP  queue SÎD
ö0z_¢+¬8sAw0Ãû, ÄsA­ 6 ùûçE8â-Ì HIGH ­8- ,.
|&8vÆ ]3 Ã90 (0, FREE ­8â,, $! ïDÜ0 8, àùÜÍùâÂö)o;8. åøËôí
/4û,ÍùÙÊÒÛ (sticky context) 0ú-, , N-Queens  Gkã>0û, N o 6,ÍùÙÊÒÛ break 0ÿ4üº fork 7 ,. 8, 11 ( -- Q6, Q8, Q11 nc) 8y»6üº fork &, EP ´¬8, Ò 0|97 . N=6, 8  ÃZ0lB2,õØÛ×ÄØÊr1ÑðùåÝ (break 0ÿÿ, &, N=6  1000 H, 8  100 H, Gk0
 trap öD×ùi) 0ü. trap öD×ù, 5+~7 . ï , UNIRED ÍùÙÊÒÛ¸ÏÒèùÜNî÷ÑÒÖ¨2¸0 GF : (ctx) , 1 $ 4 8. ,z, 10 H,z
g8 fork 8, ´¬8®â,. 6-0ÒÖØÊ0 8xÿ0. þ, 66 ÃZ, 
4,$/4,. $+, µ 8 )ü, Ã · Z%, ÈDçÑÍ÷ÊÐóù (GC) 0
réÚÁDt+0  Ã8, Û Ã \$û. 6-, GC . ¿¨0ÒDâDõÝÀ
EP Ñðùå0 trap 8ÎDö0 fork 7 ,.
(GC H¸Ó¯ GC1 HH+Zl«),) Ö£ÒÖØÊ0U 88$ü0, 2 ú+, fRÔ5,ÿ*ú,.
ÒÖØÊ0t0 fork 7 ,£'ú,. ª åøËôí Ã, vÆ  (Hybrid)Æ, ÒÖØÊ{+ (0e 03û) 0 , ¨óNîÏ  (Fine) 0ï*8. @fork 7 ,!1ú, [9] 0, ü ,ÒÖØÊ8, ¨ó Ãõ fork 0Ãû
À*0v+, call, return ÆDáæØÜ0 0, vÆ xsAïDÜäÄÀfR=13,. Öø, ÄsA­8½¿¨0 ,&, ÃN9£ fork 0Ãü)ü8ª8 call, return 0¬ó,³+i98, . $, N9ÀöÎõÓí0 C ²»'c­8,
sAx8, ¡VZéë¸, 0 SPARCstation 1(SS1)  Ã8fR8. Íùâ
fork 7 y»00b¿¨7 ,0Î.
Âô, cc(SunOS4.1.1)  gcc(version 2.6.3) 0
66, Öø0e»ûÂ ,. Öø û, ÆåÐóù -O2 ÍùâÂö8. gcc , Æ (¨ôï8²»Qt, ÎDöi(Ï åÐóù -m at(÷ÑÒÖÃÁùÜÃ0ïûû) 0y Ã1,6, ­»V¾üº fork 0=\ r4ªÆ',z8.
6, [¸7²»2Ï y²» µ 9, N), Q11 ' ÃÏÂÊö¸ (10x103

Hybrid(Q11)

Hybrid(Q11)
Fine(Q11)

Fine(Q11)

10

Fine(Q8)
Hybrid(Q6)Fine(Q6)

1

Hybrid(Q8)1x103Hybrid(Q8)Concurrency

Relative Performance100

Fine(Q8)
Hybrid(Q6)Fine(Q6)

100

10

0.5
1

10

100

Number of IUsµ 10: y),»\¿¨. ], "#q»
Number of IUs\I8ûvÆ i5»\. vÆ , y»0Äûq»\R!'Äû<¸½ µ 12: ÃP*-y»Zxÿ. Ï 
>0, y»0xûÏ N9»\0 .  Ã, y»0Äû (Q11) , B©y»0s¬7-û,.
1

1

10

100

1

Q11, 1ctx.

High Load Ratio

0.9
0.8

Q11, 4ctx.

0.7

Q8, 1ctx.

0.6
Q8, 4ctx.

0.5
0.4

Q6, 1ctx.

0.3

Q6, 4ctx.

0.2
0.1
0
1

10

Number of IUs

100µ 12, ÃP*-y»Zxÿo0
8û,. y», MP ïû,sAo, /
, ?LrÍùÙÊÒÛ¸ + Ã7ÎDö¸,z8. ï8ÍùÙÊÒÛ¸ 4. Ï , y»0ÄûB©y»0s¬7-û,. fork £0 Ãõ -6-0òý,6
01,0, ªÆxsA»\0%9 ,.

µ 11: ÄsA­8ZSÆ|9. IU <¸, ÍùÙ 7 fãÊÒÛ¸0)ý,)+33y»0ð÷7-, Ä Lazy Task Creation(LTC)[9, 5, 20] , ÖÒÊsA­8SÆ80,.
¾¼ fork j%0Ãû, ÐöåøÔØÏ0¾9, ÒÖØÊ{+ÿ* fork 7ÃÏÂÊö¸<¸]) fR0 . ÝÔØÛ ,£0|&7-. LTC , ëÐù0 ­8
.û0ú,&, 0Lç0`n¬óû ), ,$uç, ¸°7ç Ã8, h ­8â,ð÷2M fork ,ûü(, ÄUNIRED ']Ö RISC ú,6ÿ*, vÆ , C ²»l~ ,q Ã½0A¼ sA­8q9),½¿¨sAx81,Âý*-,. $, ¨óÏ )+' ?L¿¨, Öøúw0h«3û. 8ÿ8, xsA­8Ï Ã0K7-û½03, y Ã½'Äû.
µ 10, y),»\¿¨î0 . û(, ÒÖØÊ{ÿ* fork 7 ,&ÆD"#q»\ ,vÆ i5»\ áæØÜ0=1û0Öø,,.
0]ïû. ÍùÙÊÒÛ¸ 4. y»0Äû StackThreads[17] , block 0d1û³+ãDªÆ, vÆ , qR!'Äû<¸ å¨ä÷Dí0P , w« stack  Ã ,½>0 . Ï 'Äû8»0 0, Ï 6)+, N0ßDÜShN_£/1´¬8ÆDáæØÜ0=1û. 0, y»0xû Ä.90ÿ. StackThreads ' LTC NîªÆ, vÆ Ï N9»\0 . ÒÖØÊ0ïûq9),½¿¨ûü0µ 11, ÄsA­8ZSÆ0, IU <¸ Öøúw8û,0, xsA­8y»s¬)ü|9 ,ÿ0 . ©, N IU SÄs , sA­8[ ,K0Ã/-ûû.
A­8ZÆ 0, ' ÃZSo. IU <¸ øþÏ Ã0á8Ý÷çöÚDÖä
0)ý,)+33y»0ð÷7-, ÄsA­8 øD `wä, y»^_),îïõSÆx8 ,. $, ï ,ÍùÙÊÒÛ¸0 °¶T0Hg ,&, Throttle Mechanism[12],k-bounded loops[3] y»º¹ø0Ã)ý,, ÄsA­8SÆ7*x8 ,.

/-1. Q, [12] , LTC Nîuç/ °7ç0 ÃsA­8+9ý,0
K7-þ+, Öøh«[0°û0, ÚDÖäøD `=13)08û,0, von Neumann 7 `0çDÒ ,Öø,,.
0, 0YÚDÖäøD `, Ý)+' !û thread i(N_0+, 6 thread 0
von Neumann 7åøÔØÏq Ã , Multithreaded Architecture |981 [1, 8, 14].
$, Threaded Abstract Machine[4] , ÚDÖäøD `¿1[¸7²» Id 0, w«åøÔØÏ½3 Ã ,£08. 6-*ø
þ4, thread wS, Öøþ4,xsA­8Ï ÃÍ900, ÄsA­8
'Ï Ã0/4,ûü0,û,.
8rpk

ÖÁ, Ï Ãþ4,½I, ÒÖØÊ0ïû)+üq90#%Æ/ , ÃsA­879+9ý,, vÆ Ã
|&0Ã. PIE64  Fleng 0ïû (, o;0Ã>, (1) i5åøÔØÏ Ã,Ï y²»þû', N9ÀöÎõÓíC ²»¢ÿ-åøËôí R!1 ®û»\0A¼1,6, (2) y»0§wÄûªÆ, ! y Ã)Äû<¸½>0P*,6, (3) y»0xûªÆ, i5»\6 ,<¸½>xû', Ï y Ã),³J
N9. ¿¨0P*-,60PX8.

7ðê

[1] B.S. Ang, Arvind, and D. Chiou: StarT the Next
Generation: Integrating global caches and data ow
architecture, CSG Memo 354, Lab. for Computer
Science, MIT, 1994.
[2] T. Araki, Y. Hidaka, H. Nakada, H. Koike, and
H. Tanaka: System integration of the parallel inference engine PIE64, Workshop on Parallel Logic
Programming, FGCS94 pp.64{76, 1994.
[3] D.E. Culler: Managing parallelism and resourcesin scienti c data ow programs, PhD thesis, Dept.
of EECS, MIT, 1989.
[4] D.E. Culler, A. Sah, K.E. Schnauser, T. von Eicken,
and J. Wawrzynek: Fine-grain parallelism withminimal hardware support: A Compiler-Controlled
Threaded Abstract Machine, ASPLOS-IV, pp.164{
175, 1991.
[5] M. Feeley: A message passing implementationof Lazy Task Creation, Parallel Symbolic Computing : Languages, Systems, and Applications,

US/Japan Workshop Proceedings, LNCS 748, pp. 94{
107, Springer-Verlag, 1992.
[6]
,
,
:
" #%2)2 PIE64 3 #1.+-3$5&,'*0, 67! CPSY90-44,
pp. 37{42, 1990.
[7] Y. Hidaka, H. Koike, and H. Tanaka: Architectureof Parallel Management Kernel for PIE64, Future
Generations Computer Systems, Special Issue on
PARLE92, Vol.10,No.1,pp.29{43, 1994.
[8] R.A. Iannucci: Toward a data ow / von Neumannhybrid architecture, ISCA88, pp.131{140, 1988.
[9] E. Mohr, D.A. Kranz, and R.H. Halstead, Jr: Lazy
Task Creation: A technique for increasing the granularity of parallel programs, ACM Symposium on
Lisp and Functional Programming, pp.185{197,1990.
[10] S. Murakami, H. Nakada, Y. Hidaka, H. Koike,and H. Tanaka: Load distribution system of PIE64,
Workshop on Parallel Logic Programming, FGCS94
pp.77{90, 1994.
[11] M. Nilsson and H. Tanaka: Massively parallel
implementation of Flat GHC on the Connection
Machine, FGCS88, pp.1031{1040, 1988.
[12] C.A. Ruggiero: Throttle Mechanisms for the Manchester Data ow Machine, PhD thesis, UMCS-878-1, Dept. of Computer Science, Univ. of Manchester, 1987.
[13] S. Sakai, K. Okamoto, H. Matsuoka, H. Hirono,
Y. Kodama, and M. Sato: Super-threading: Architectural and software mechanisms for optimizing parallel computation, International Conference on Supercomputing 93, pp.251{260, 1993.
[14] S. Sakai, Y. Yamaguchi, K. Hiraki, Y. Kodama,
and T. Yuba: An architecture of a data ow single
chip processor, ISCA89, pp.46{53, 1989.
[15] K. Shimada, H. Koike, and H. Tanaka: UNIREDII:
The high performance inference processor for theparallel inference machine PIE64, New Generation Computing, Vol. 11, No.3,4, pp.251{269, 1993.
[16] 9,,:" #/(2 PIE64 3; :<3 84 , #, Vol. 32, No. 7, pp.867{
876, 1991.
[17] K. Taura, S. Matsuoka, and A. Yonezawa: StackThreads: An abstract machine for scheduling negrain threads on stock CPUs, JSPP94, pp.25{32,1994.
[18] K. Ueda: Guarded Horn Clauses, ICOT Technical Report TR-003, ICOT, 1985.
[19] K. Ueda and T. Chikayama: Design of the Kernel Language for the parallel inference machine,
The Computer Journal, Vol. 33, No. 6, pp.494{
500, 1990.
[20] I. Watson: SLAM - Lazy Task Creation and Dynamic Load Balancing with Active Messages, Draft
Internal Report, Dept. of Computer Science, Univ. ofManchester, 1993.

      $ 