Japan Advanced Institute of Science and Technology

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

Author(s)

Citation

Issue Date

Type

Text version

URL

Rights

Description

Massively Parallel TRAM

based on Parallel TRAM

Hiromichi Hirata

Scho ol of Information Science,

Japan Advanced Institute of Science and Technology

February 13, 1998

Keywords: parallel term rewriting, abstractmachines, TRAM,ParallelTRAM,

messagepassing.

Intro duction

Wecan use algebraic specication languages suchasOBJ3 and CafeOBJto writeformal

sp ecicationsof softwareand/orhardwaresystems. Algebraicsp ecication languagesare

usually executable, we can verify some correctness of the sp ecications and can reason

ab out some prop ertiesof the systems through the sp ecications (semi) automatically by

usingcomputers. Sincethesp ecicationscanbeexecutedasprogramsinthespecication

languages, we may use the sp ecication languages as rapid prototyping to ols. Many

algebraic specication languages are based on (order-sorted conditional) term rewriting

systems (TRSs) as a general computational model. To implement the rewrite engines

eciently on conventional computers, abstract machines for term rewriting systems are

designed. TRAM (Term Rewriting Abstract Machine) is one of these abstract machines

thatadoptstheE-strategyasitsreductionstrategy,whichmakesitp ossibletocontrolthe

reduction reasonably. ParallelTRAM is a parallelversion of TRAM, whichadds ability

of parallel rewriting toTRAM. It has the parallel E-strategy that is an extension of the

E-strategy,and can control the parallelism ofthe reduction suitably.

On the other hand,nowadays, since hardwaretechnologiesare enhanced rapidly,and

parallelpro cessinghas comeintowideuse, a workstationclusterhas b ecomesp opular to

realizetheparalleldistributedenvironmentseconomically. Furthermore,recentmassively

parallelcomputers haveb een used to various areas, includeTRSs.

Copyrightc 1998byHiromichiHirata

rewrite engines eciently on massively parallel computers and/or workstation clusters.

Our approach, we have massively parallelized TRAM based on Parallel TRAM so that

the rewrite engines can be implemented eciently on the massively parallel computers.

In addition, we have implemented the massively parallelized TRAM (Massively Parallel

TRAM) on the Cray T3E which is a massively parallel computer, and have evaluated

the p erformance of the implementation by executing several b enchmark programs on

MassivelyParallelTRAM.

Massively Parallel TRAM

The characteristicpoints of the MassivelyParallelTRAM are as follows:

The Massively Parallel TRAM is designed to b e executed on massively parallel

computers and/orworkstation clusters.

The Massively Parallel TRAM adopts the message passing mo del as its parallel

computational model.

Thesimplemaster/workermodelisusedasthebasicparallelalgorithmforMassively

ParallelTRAM.

The master maintains three pieces of information about workers, and each worker

ishas the three states: idle, busy and waiting.

In the Massively Parallel TRAM, the reference table called INFO is put into the

Strategy List.

Design

Since ParallelTRAM wasoriginally designed to b e executedon multiprocessors, itspar-

allel computational mo del was the shared-memory model. However,it is dicult to im-

plement MassivelyParallel TRAM by using shared-memory mo del on massively parallel

computers and/or workstation clusters. On the other hand, the message passing model

canb eappliedtomanykindsofparallelarchitecture. Therefore,wehavedecidedtomake

use of the message passing model as the parallel computational mo del of the improved

TRAM.

To manage the load of works on the processors, the simple master/worker model is

used as the basic parallelalgorithm. The model is generally used to managethe process

by using message passing. In the model, a parallel workis scheduled to workeciently

byahost pro cessor,this host pro cessoris calledmaster,and theprocessor inthe parallel

workis calledworker.

The master has three pieces of information ab out workers. Each worker has the three

states: idle, busy and waiting. Just after b ooting Massively Parallel TRAM, allworkers

arethe idlestates. Themasterholdsallthe idleworkersinIdleStack. Theworkerswhich

is rewriting terms are the busy states. A busy worker may ask idle workers to rewrite

some subterms, and wait to receive the results of the rewriting from the workers. The

workerswaitingthe results from other workers are the waitingstates. The master holds

allthe waitingworkersinWait List. Notonly idle workersbutalso waitingworkersmay

undertaketasksfrom busy workers.

INFO:Reference Table

Since Parallel TRAM was originally designed to b e executed on multiprocessors, inter-

pro cess memoryaccess hadnoproblem. On the otherhand, Massively ParallelTRAMis

designedtob eexecutedonmassivelyparallelcomputersand/orworkstationclusters,thus

itsparallel computationalmodel isdistributed-memorymodel. Accordingly,an interpro-

cess memory referenceshavesome problem; some pro cess must havesynchronizationfor

garbage collection, etc. Because this problem may be serious overhead for the p erfor-

mance of term rewriting, wemust removeinterprocess memory references. We make use

of reference table calledINFOthat extends the StrategyList.

Conclusion

We have improved Parallel TRAMfor massively parallel computers and implemented it

on Cray T3E has 128 pro cessing elementsby using the message passinglibrary MPI(the

Message-PassingInterface). Weobtained following results:

We parallelized TRAM very massively by using a concept of Parallel TRAM on

distributed memorycomputers, without losing the advantages of TRAM.

Sinceweimprovedthemessagepassingmo delbyusingINFO,wecancollectgarbage

asynchronous.

The maximum p erformance of Massively ParallelTRAM was 67 times as faster as

the performance of TRAMwhen it was executedwith 127 workers.