EIJKLFNPHQSUXVFleng TOGVRYDWMC`d lv, n ,  ;vZ¥ k¥¡=Zy} 7{3{1Fleng º Comitted-Choice hi¹:³µ, rÃpzÄ§qbÁj¬¹hiµ¨½. ÍÔÆÑÎ¸^s¯½´¹zÄeÀß<_µ¨½]ÀØ³. }mµº, ÏÐÒzÄ×¦c¸zÄÑÕÉÅÎÇÈËÎÀÜ®, Þ ¹ÚÑÕÉÅÎÇÈËÎ¶t¤®
±. °¹>, queen µ 4 ÈÓÊÌÙ¸ 89% ¹p©ÈÓÊÌÂÀÜg®, 2.77 a¹jc«\¼¾±. :{µ, primes µºw?xÖ«o·¿¾·©«~¼ª¸·²±. ­¹¹¢{|¹:³¶®´, w?xÖ{ÛÀ£®±Ý|ÀÜ®, w?xÖ{Û£¹±»¹uÜfÀo·©, [Ào·²±.

Implementation and Evaluation of Fleng Run-time System
on Shared Memory Parallel Computers

Tsunehiko BABA, Takuya ARAKI, Hidehiko TANAKA
School of Engineering, the University of Tokyo
7{3{1 Hongo, Bunkyo-Ku, Tokyo

Fleng is one of committed-choice languages and a ne-grained highly parallel symbolic
processing language, which has a high ability to extract potential parallelism from anyprograms. In this paper, we have implemented Fleng run-time system on shared memory
parallel computers and have evaluated its performance by comparing it with sequential
run-time system. These evaluations make it clear that this run-time system has a higheciency rate in N-Queen and Gauss, but does not work well in Primes.We proposed
an improved load balancing method in order to solve this problem and we preliminarily
examined this method.

1 GHC, KL1 xr¢.
Committed-Choice ÒRY, 8(ûõÁ8+X&4HX1tu_¥s¢}¡, XF(rõ) qS¢ú ø¥s, 6HD>4o¢ú ø¥C5¢}x2 r¢. x, %Â9ú ø¥C5¢}xy¢.
Fleng 6HD> ,åàèãú 6HD=JRY©Öþñw 62 ÷ £¢. (, @%à0[{©Ö£RY¥8X", ú ÖufFú /¥cRYr¡, t(jáw ú Öu0p¥a7, jáw ©ÖVa£RYr¢. Qo, 4RYVmø
Qw -8X"/4s¢RY®.r¡, Áñ  HPF (High Performance Fortran) ýxr¢. w, äN¡dú ÖuÈxd¢}3÷au £¢}r¡, ®.÷ £¢RYM@%à0[{RYr, ú Öu[{fF
3÷ú T¥C5¢}x5s, W.÷ £¢RYr¢ÜÉðøds.
}tÓw , zÜÉ+ú Öur
¢0X-%4,y6ÜÉ¥cy. %4,y6, Committed-ChoiceÒRY Fleng ¥a [2], WÜÉ¥cy [6] [3]. }£ ÜÉB Fleng ò0xc
¤£ys¢x, Fleng ¥d¸-c¢N©Ö£ú ó< J PIE64 [1] ëò0¥cs¢x¼s.
}, zÜÉË?@EÒú Öu (<F(6H$)IX"*X CJ) ë Fleng à0Ô¥-³, szw8J(<X¡ ò0¥c. , ò0Ù3w -³DJ&> "*>ÄQsÛþ. , ô5÷þ(_¯r¢î-L¥cs,a¥c.
"., Ã 2é, Fleng zÜÉ-³¥cË?@EÒú Öuëà0Ô-³þñs«¢. ¹s, Ã 3é-³à0Ôò0ÇÛþ¥ct. Ã 4é®é wÄQ¥\Ø¢_¯1ÿr¢î-Lò0s7¢. jWÃ 5ér¢.
12Flengfoo(A,R) :- add(A,1,B), mul(B,2,R).

st R = (A + 1) 3 2 ¥Ö¢6HD>¥au¢.
}6HD>, A = 1  foo(1,R) ¥-c¢, add(1,1,B), mul(B,2,R) st 2 
XFâymu £, ££¥ú -c¢. w, }ìf, mul(B,2,R)  add(1,1,B) Ù3 B xØK£s-cys, ØK£¢à0¥B: ("9J-) , ØKWà0¥ia¢. }t+X&4HX1t¥s°XF¥ú -c¢}¡, z,N@%õ÷¥ãs, °õ÷¥ú -c¢}x2 r¢. }u_¥-Q¢, ûõ8(Á8r¡, âymu¢}ys. ûõ<xØsswØs¢w 2 î¿¥, (TØu, <xû¤¢}~s.
ò 1 Fleng -c@+F¥&. }òt
, Fleng -c,
1. 7)-B.4X CJ
2. :+XXF4X¥-cyXFx~z¢Ñ¡ü.
Arbitrarily Selected Goal

Suspendâ Fleng 

Wait for binding

Activate

Binding
Variables

New
Goals

Body
ReductionFailò 1: Fleng -c@+F

 FlengFleng zÜÉ+©Ö£m6Tdú weà0[{6HD=JRYr¡, CommittedChoice ÒRY, ú 0ÒRY(r¢. J&)" Prolog 8z"s¢x, 1)
,D)¥c¤sstQ, $<J*"Âyz&¢. Committed-Choice ÒRY, »2.1

UserGoal Pool

CommitHead Unification

Top Goal

Goal Scheduling

Committed-Choice¢£¥
Fleng 6HD>x-c ¢|à04£%e;bw _ù£¢.
2.2

2.2.1

2

Fleng¢t. w, ë7t?@EÐq¥Ë¢, XF"&)Ë£v¡,
úüø¥ý, $"$ »÷Xxð¢.  , XF"&)$""c, ûõd¸, ?@EHX CJý »÷Xxð¢. }t »÷X P "G)D5DE¥s, -Q¢.
²9³¯´° Ë?@EÒú Öu[{ô5÷1ÿ, e"G)-{XFAXô
5÷XFAX62 ¥s¢1ÿ¥k [5].
LGS (Local Goal Stack) e"G)-~©{ £SÂyXF"&), GGS(Grobal Goal Stack) °"G)-Ë¢ô5÷XF"&)r¢. LGS  GGS
".t0p¥¢. (ò 2)<HPa6E6H$)
w7ø¥[ë¢s £s¢<H¥Pa, Þô Fleng RY¶6HD>ûm¥ct.
2. 6T÷X6E6H$)
}6E6H$)Z2[ë¥Nv¡, <H¥Pa Fleng 6HD>¥8, 6T¥ûu Fleng 6HD>¥5 ¢.
3.J2D<H¥Pa / 6T÷X¥cW Fleng
6HD>¥8 , C RY6HD>
J2F, 5 ¢.
4. DJ&> "*>Fleng 6HD> z, Fleng J2D¡5 £ C RY6HD>¥J2
F5!,X-¥3g, eÖ
-cß"!AXEJX8!GCJ (GC, Garbage Collection) ¥sà0¥ct.
z`, 4 êDJ&> "*>Ë?
@EÒú Öuë-³¥c. ".³à0Ô-³þñs7¢.
¬­©¦«§¨ª«®±¡´¤Ë?@Eú Öu, SunOS 5.X x0
p2 <F(6H$) WS(Work Station) ¥¾ê-³¥c. }£, <F(6H$)
 WS xú nÌëhN!0r¡, \zs £s¢}, »RYëhx%y¢r¢.
z-³0Ô-³þñds4@%Ò
à0Ô'sw ".&.
8 ¾ê OS  SunOS 5.X "G)-D5DE¥ks¢. }D5DE¥s, "G)-ûùV§À¥cs, <F("G)-¢ú -c¥-Q¢. , zà0Ô, e6H$)X LWP (Light Weight Process)¥j¡ó{, e LWP {e"G)-¥1J-¢}¡, e"G)-x&¢6H$)j¡ó{¢t, "G)-Z2N-c¥ct.
?@EÐq°"G)-Ës¢. }, GC (k°"G)-1$c¤£¢.
, <F("G)-/¡, XF"&)w
öõ"G)-x1$XF¥6) AV;)6
1.

:

Fleng:

Fleng:

:Goal
3-(a)

2-(a)

threadthread

Goal
Goal
Goal

2.2.2

Goal
2-(b)
Goal
Goal

Goal

LGS(Empty)

Goal

Goal

GGS

LGS(Full)ò 2: ô5÷þ( (LGS 0p)*8,XF6) A(a) GGS XF¥6) A¢.
2. E' CJXF6) A(a) LGS Ðyxr¢ìf ï
XF¥6) A¢.
(b) LGS x($, LGS LXF¥( GGS 6) A, Ðy¥pw, LGS ïXF¥6) A¢.
3. XF;)6
1.

Multithread3XFx8s¢ìf LGS w;)6¢.
(b) LGS xÐìf GGS w ;)6¢.
»"G)-ú -c¢z, '÷@%-c¢ìf, '÷xE' CJXF¥ LGS 6) A£8s. }£¡,}ô5÷þ(%tQ¥#.
 GGS "G)-qË£s¢, $"¾¢ »÷Xxðx, LGS "G)-T, »"G)-
¢$"xx} , »÷Xðxs.
, GGS $"xP£, »÷X¢X1X7)-xPæ¢.
 LGS SÂy GGS ë, _µxp8$"xd¸r¢.

Gauss ÿ¢3 1 %þM(\ÿ¥ct6HD>r¢. 3:), (pivot) ­Å¥c¤sþÿ\ÿ¥s¢. 8(Á8ûõ¢X1X7)-¥qP¢²âmu ^Á8¡-Qs¢[4]. 80 2 80 c \¥È¢. 6HD>ú øBMTr¢.

(a) LGSgauss:ñ 1: primes -c¸T (N = 10000)
"G)-õ
124@%
0.67(s){{(1.82)
1.22(s)(1.00)z-³
1.23(s) 1.24(s)(ú )(1.01) (1.02)
ñ 2: queen (N = 11) -c¸T"G)-õ
124@%
3.43(s){{¹»ä½¿@
3.1 ¿@-³DJ&> "*>¥s¸T·K¥
c. , -³à0Ôø ò0¥ct
, 4@%Ò Fleng DJ&> "*>
-c¸Tëh¥c.
·KnÌ".H¡r¢.
3:
Sun Enterprise 3000(4 CPU

Architecture(1.38)
4.74(s)(1.00)

z-³
2.82(s) 1.72(s)(ú )(1.68) (2.76)
ñ 3: gauss (N = 80) -c¸T"G)-õ
124@%
2.59(s){{z-³(ú )_ù).

:SunOS 5.5.1 (OS),Pthread 1.13 (Library),gcc 2.7.2 (C Compiler)(1.30)
3.36(s)(1.00)

2.06(s)(1.63)

1.25(s)(2.69)

SoftwareAæµ££6HD>s·KÙ3¥ñ
1, ñ 2, ñ 3&. e·K 5 ]-cìfùÎ<r¢. , kU4õ<-³DJ&> "*>v{¢ 1 "G)-$¸T¥ 1.00 úv/¸Tër¢.
, @%DJ&> "*>¸T¥ëh¢. 1 "G)--c$¥Ý¢, e6HD>@%DJ&> "*>-c¸T¡?
z, jÂ 55% ¸T (primes) w-c¸Tx5
ss. }£, 1 "G)-r¢r¤ ,»÷Xu_¥-cs¢r¢.
%, ú øxdsò06HD>rau¢. weà0[{ queen , 2 "G)-$
1.68 , 4 "G)-$ 2.76  ¸T[ëx, (þ, õ<-[{ gauss , 2 "G)-$
3.2

, ò06HD>weà0õ<62 w ­, ®. primes, queen ¥W. gauss Ö 3 6HD>¥s.
££6HD>".H¡r¢.
YD,"*/"¢sZ1ÿ¥s²õ ¥s¢6HD>r¢. N = 10000²õ ¥È¢. 6HD>ú ø
Is.
N-Queen Ä\¥°\9¢6HD>r¢. 11 2 11 <"$\¥È¢. 6HD>ú øxds.
primes:queen:4ñ 4: -³à0Ôv{¢ N-Queen Ä (N = 11) -c$q"G)-õ -c$q P ut P st P(ut + st ) -Z"G)-õ1
2
44.74(s)2.82(s)1.72(s)ii

4.69(s)5.29(s)5.57(s)0.04(s)0.19(s)0.56(s), 4 "G)-$ 2.67  ¸T[ëx, Ý£v¡, öõ CPU ¥s¢}¸T[ë¥g9¢}xy.
, "G)-xZ2N0ps¢ws
, ò06HD> queen -c$q"G)- ix usertime(ut ), systemtime(st ) Aau¢ (ñ 4). -c$q-nÕ7$qr¡, "G)-{ usertime, systemtime  CPUxçì$qr¢. -Z"G)-õ, %Ö(5£¢.
X(ut + st )=-c$q}(w , 2 "G)-$ 97%, 4 "G)-$ 89%"G)-x4ÿv¡, ds"G)-2¥-Qs¢}x¤w¢. 4 "G)-$4ÿ2xPæs¢0, Network ¨¹£WS ¥s¸TÖ·¥cs¢, DJ&>"c&"x-c£s¢*Íxau £¢.
·K$ »&"¥y¢{-cstD$x, l°0¡ãz}yse"G)-x° CPU ¥¬¢}xyssr¢.
(þ, ò06HD> primes vs, CPUõx´1¸T[ëxÝ £ss. }£primes ú øxIs 1 "G)- LGS
4õwXFxºo, Ù3 1 "G)-w0pssr¢. ú øIs6HD>¥ú -c¢ïô5÷þ(¥Ûþxðr¢.
ii

4.73(s)5.48(s)6.13(s)

1.00
1.94
3.56

ÂyxjOr£, ô5÷*¢ /jåS5¢}x2 r¢. w, 6HD>2 ¼ø6H
D>;b¥-cs¢w¥=¢}5z, -Q1ÿö¢.
2. '÷'ð LGS  GGS xÐìf, »"G)- LGS w G¨XF¥0¢þÿ.
}1ÿ XF¥0¡5¾ê¢"G)-ØKþÿ.
 "G)- LGS Bw 0¡5XFØKþÿ.
sQs, a¢ðxr¢.
, ×Q1$öõ"G)-x1( LGS ¥$"¢2 øxr¡, LGS
$"¾¢ »÷Xxð}r¢. }£¡'÷'ð LGS  »÷X¥ct}¡, X1X7)-xût.
3. XF¥6) A¢l, GGS xÐ
Js¢"G)-xºoìfGGS 6) A¢þÿ.
}1ÿ, GGS î¿¥o!¢}xð¢x, O} »÷X¥ctÂyX1X7)-¢, O}H)¥c¤s ag ¥ûù¢}]í
¥ct}xy¢.
ë71ÿtëhN%-³2  3 ê1ÿs, -³¥c. ïz-³ô5÷þ(Ï½N".H¡r¢.
 ag ¢ LGS î¿o!
LGS î¿¥ñ ag ¥s, "G)-î¿¥o!¢. } ag °"G)-w è£¢. LGS ¥ O}o!¢,»÷Xxð¢x, X1X7)-xÂ

1.63

ii

LGSii

ÀBÁ·Ã¸äÄºãÅáéÆ¾¹
4.1 ÄºÃ¸ä¼ú Tå6HD>vsú 0p
d¸/¢ô5÷þ(_¯1ÿsau¢.
Ï½N, ".þ(xau £¢.
1. LGS #¥-c$jO<û^¢þÿ
45yz¡, Ä¢. }, X1X7)-¥qP¢ ag  »÷Xs.
 E' CJXF6) A6) A¢n, ag g9¥ct. Js¢"G)-xºo¢ , XF¥GGS 6) A¢.
 XF;)6
LGS xÐr¢ìf ag <¥âymu,e"G)- LGS î¿¥+¢.

7, -³à0Ô¥sò0¥c.
dsú ø¥¢ò06HD>vs,
ô5÷xZ28zc¤£, 4 "G)-$"G)-2 89% ¥-Q, 2.88 ¸T[ë¥2.
w, (þú Txåò06HD>r, ô5÷xc¤£¸T[ëxÝ £sÄQxÝ £.
}ÄQ¥\Ø¢ïô5÷1ÿ¥QoÛþBr¢. î-L¥cs aÄQs7.
hW6Ä, î-LÄQ\ØþÿÛþÇ, »ô5÷1ÿr¢Ûþe1ÿëhVÛþ¥csz}xr|£¢.

Æ¾¹â¿@®ª7ô5÷þ(¥-³, îNLò0¥c. ò0íÚÃ 3é1r¢. Ù3¥ñ 5&.
M"!AXEJ1ÿëh¢, 4 "G)-$ primes  1.13 [ëxÝ £, queen vsû s¸T¸T[ëx2 £. w
, (þ gauss  2 "G)- 10%, 4 "G)- 40% ¸TI.xÝ £, 4 "G)-$2 "G)-$¡-c$qx´Âs¢.
N) system time KE´ÂxÝ
£ (ñ 6), system time x user time ¡Ns¢}xr| £¢. sytem time x´Â¢0sszw)xau £, Qo, e)r+X&¥·KÛþBr¢.
4.2

¶Â
[1] Takuya Araki, Yasuo Hidaka, HidemotoNakada, Hanpei Koike, Hidehiko Tanaka. System integration of the paralle inference engine PIE64. In Workshop on Parallel Logic
Programming attached to International Symposium on Fifth Generation Computer Systems 1994, Dec, 1994.

[2] Nillson,M. and Tanaka,Hqueengauss

1.23(s)(1.00)
4.66(s)(1.00)
3.40(s)(1.00)

1.25(s)(0.98)
2.76(s)(1.69)
2.53(s)(1.34)

ULogic Programming'86, LNCS264, Spriger-verlag, 1986

log Machines, In Wada, E.(Ed.)

U[3] b Æ, RB,ï. Committed-Choice ÒRY Fleng v{¢¦N6TjO/. 6HD=JÜÉ[ 96-PRO-8, pp.109 - 114, Aug, 1996.
[4] Â (. Committed-Choice ÒRY Fleng v{¢ ¦N3XãÊ. ii#ø,ñ 5: ïô5÷þ(-c$q"G)-õ
124primes

U Fleng Prolog - Thelanguage which turns Supercomputers into pro-1.09(s)(1.13)
1.68(s)(2.77)
2.80(s)(1.21)March, 1997.

ÜÉÁñ. RB,ï. Ë?@E<F(6H$)ë FLENG à0Ô Âv=)à0"*>ÜÉ, pp.249 - 269, x11, Febrary, 1991.
[6] 7d], å>ù, RB,ï. PIE64 v{¢öf6Tú à0¥sjO6T÷X { m6Tú ±6Tú ; 6&,ö`÷
1f. ú à0 J;!> JSPP '95,
[5]

ñ 6: gauss(N=80)  system time"G)-õ1
2441ÿ 0.00(s) 0.22(s) 0.43(s)î-L 0.00(s) 0.53(s) 3.35(s)pp.115 - 122, May, 1995.

çâèzÜÉ, Committed-Choice ÒRY Flengà0Ô¥Ë?@EÒú Öu-³1ÿs56