ForkPerfTest.mesa
Copyright Ó 1993 by Xerox Corporation. All rights reserved.
Created by Christian Jacobi, May 13, 1993
Christian Jacobi, June 8, 1993 5:35 pm PDT
Test program to measure speed of forks, parallel processing and similar operations.
For measuring, a quicksort algorithm is used. Quicksort is a good thing to measure because it is neither specially well suited to parallelism nor does it need lots of communication.
While this is about parallelism, the individual test are not re-entrant and only one at a time should run.
DIRECTORY BasicTime, Commander, CommanderOps, Convert, ForkOps, IO, Process, Random, Rope, WorkerThreads;
ForkPerfTest:
CEDAR
MONITOR
LOCKS rp USING rp: REF Pair
IMPORTS BasicTime, Commander, CommanderOps, Convert, ForkOps, IO, Process, Random, WorkerThreads =
BEGIN
constantSeed: INT = 123456;
seed: INT ¬ constantSeed;
Value: TYPE = INT;
maxSize: INT = 200290; --of the array allocation for the array to be sorted
defaultSize: INT = 100290;
size: INT ¬ defaultSize;
array: REF ARRAY [0..maxSize) OF Value ¬ NIL;
simpleSizeLimit: INT ¬ 8; --at least 3
forkSizeLimit: INT ¬ 3000;
Pair: TYPE = MONITORED RECORD [low, high: INT ¬ 0, done: BOOL ¬ FALSE, waiters: CONDITION];
forksCnt: INT ¬ 0; --counts the "Forks"
counterLock: REF Pair ¬ NEW[Pair];
CountFork:
ENTRY
PROC [rp:
REF Pair ¬ counterLock] = {
forksCnt ¬ forksCnt+1
};
WaitDone:
ENTRY
PROC [rp:
REF Pair] = {
WHILE ~rp.done DO WAIT rp.waiters ENDLOOP
};
SetDone:
ENTRY
PROC [rp:
REF Pair] = {
rp.done ¬ TRUE; NOTIFY rp.waiters
};
startPulses: BasicTime.Pulses;
SetUp:
PROC [dontArray:
BOOL ¬
FALSE] = {
IF array=NIL THEN array ¬ NEW[ARRAY [0..maxSize) OF Value];
IF ~dontArray
THEN {
IF seed#0
THEN {
rs: Random.RandomStream ¬ Random.Create[seed: seed];
FOR i:
INT
IN [0..size)
DO
array[i] ¬ Random.NextInt[rs];
ENDLOOP;
}
ELSE {
FOR i:
INT
IN [0..size)
DO
array[i] ¬ size-i;
ENDLOOP
}
};
forksCnt ¬ 0;
startPulses ¬ BasicTime.GetClockPulses[];
};
Report:
PROC [s:
IO.
STREAM, what: Rope.
ROPE, dontTestOrder:
BOOL ¬
FALSE] = {
elapsedPulses: BasicTime.Pulses ¬ BasicTime.GetClockPulses[] - startPulses;
time: REAL ¬ BasicTime.PulsesToSeconds[elapsedPulses];
IO.PutF[s, "%g time: %g seconds", IO.rope[what], IO.real[BasicTime.PulsesToSeconds[elapsedPulses]]];
IF forksCnt#0 THEN IO.PutF1[s, " forks: %g", IO.int[forksCnt]];
IO.PutRope[s, "\n"];
IF ~dontTestOrder THEN TestOrdering[];
};
SimpleSort:
PROC [low, high:
INT] = {
FOR i:
INT
IN [low..high)
DO
FOR j:
INT
IN (i..high]
DO
IF array[i] > array[j]
THEN {
x: Value ¬ array[i]; array[i] ¬ array[j]; array[j] ¬ x
};
ENDLOOP
ENDLOOP
};
Partition:
PROC [low, high:
INT]
RETURNS [
INT,
INT] = {
m: INT ¬ (low+high)/2;
x, bval: Value;
IF high-low<3 THEN ERROR; --bith, the simple sort and the main loop could bounds fail
SimpleSort[m-1, m+1]; --not for real; just gives a better average bval
bval ¬ array[m]; --quite random
DO
WHILE array[low] < bval DO low ¬ low+1 ENDLOOP;
WHILE bval < array[high] DO high ¬ high-1 ENDLOOP;
IF low > high THEN RETURN [high, low];
x ¬ array[high]; array[high] ¬ array[low]; array[low] ¬ x;
low ¬ low+1; high ¬ high-1
ENDLOOP;
};
QuickSort1:
PROC [low, high:
INT] = {
IF high-low<simpleSizeLimit THEN SimpleSort[low, high]
ELSE {
lBound, hBound: Value;
[lBound, hBound] ¬ Partition[low, high];
IF low<lBound THEN QuickSort1[low, lBound];
IF hBound<high THEN QuickSort1[hBound, high];
};
};
QuickSortComp:
PROC [rp:
REF Pair] = {
--Comp means use NEW for compensation
IF rp.high-rp.low<simpleSizeLimit THEN SimpleSort[rp.low, rp.high]
ELSE {
lBound, hBound: Value;
[lBound, hBound] ¬ Partition[rp.low, rp.high];
IF rp.low<lBound THEN QuickSortComp[NEW[Pair ¬ [low: rp.low, high: lBound]]];
IF hBound<rp.high
THEN {
rp.low ¬ hBound;
QuickSortComp[rp];
};
};
};
QuickSortFORK:
PROC [rp:
REF Pair] = {
IF rp.high-rp.low<simpleSizeLimit THEN SimpleSort[rp.low, rp.high]
ELSE {
process: PROCESS ¬ NIL;
lBound, hBound: Value;
[lBound, hBound] ¬ Partition[rp.low, rp.high];
IF rp.low<lBound
THEN {
np: REF Pair ~ NEW[Pair ¬ [low: rp.low, high: lBound]];
IF lBound-rp.low>=forkSizeLimit
THEN {process ¬ FORK QuickSortFORK[np]; CountFork[counterLock]}
ELSE QuickSortFORK[np];
};
IF hBound<rp.high
THEN {
rp.low ¬ hBound;
QuickSortFORK[rp];
};
IF process#NIL THEN TRUSTED{[] ¬ JOIN process};
};
};
QuickSortFork:
PROC [x:
REF
ANY] = {
rp: REF Pair ~ NARROW[x];
IF rp.high-rp.low<simpleSizeLimit THEN SimpleSort[rp.low, rp.high]
ELSE {
np: REF Pair ¬ NIL;
lBound, hBound: Value;
[lBound, hBound] ¬ Partition[rp.low, rp.high];
IF rp.low<lBound
THEN {
np ¬ NEW[Pair ¬ [low: rp.low, high: lBound]];
IF lBound-rp.low>=forkSizeLimit
THEN {ForkOps.Fork[QuickSortFork, np]; CountFork[counterLock]}
ELSE QuickSortFork[np];
};
IF hBound<rp.high
THEN {
rp.low ¬ hBound;
QuickSortFork[rp];
};
IF np#NIL THEN WaitDone[np];
};
SetDone[rp];
};
pool: WorkerThreads.Pool;
activities: LIST OF WorkerThreads.Activity ¬ NIL;
activitiesLock: REF Pair ¬ NEW[Pair];
Remember:
ENTRY
PROC [a: WorkerThreads.Activity, rp:
REF Pair ¬ activitiesLock] = {
activities ¬ CONS[a, activities]
};
Fetch:
ENTRY
PROC [rp:
REF Pair ¬ activitiesLock]
RETURNS [list:
LIST
OF WorkerThreads.Activity] = {
list ¬ activities;
activities ¬ NIL;
};
QuickSortWorker:
PROC [x:
REF
ANY] = {
rp: REF Pair ~ NARROW[x];
IF rp.high-rp.low<simpleSizeLimit THEN SimpleSort[rp.low, rp.high]
ELSE {
lBound, hBound: Value;
[lBound, hBound] ¬ Partition[rp.low, rp.high];
IF rp.low<lBound
THEN {
np: REF Pair ~ NEW[Pair ¬ [low: rp.low, high: lBound]];
IF lBound-rp.low>=forkSizeLimit
THEN {Remember[WorkerThreads.Fork[pool, QuickSortWorker, np], activitiesLock]; CountFork[counterLock]}
ELSE QuickSortWorker[np];
};
IF hBound<rp.high
THEN {
rp.low ¬ hBound;
QuickSortWorker[rp];
};
};
};
QuickSortWorkerBase:
PROC [p:
INT] = {
activities ¬ NIL;
pool ¬ WorkerThreads.CreatePool[percentage: p];
QuickSortWorker[NEW[Pair ¬ [low: 0, high: size-1]]];
FOR list:
LIST
OF WorkerThreads.Activity ¬ Fetch[activitiesLock], Fetch[activitiesLock]
WHILE list#
NIL
DO
WorkerThreads.Wait[list];
ENDLOOP
};
QuickSortOptimum2Comp:
PROC [x:
REF
ANY] = {
process: PROCESS ¬ NIL;
rp: REF Pair ~ NARROW[x];
lBound, hBound: Value;
[lBound, hBound] ¬ Partition[rp.low, rp.high];
IF rp.low<lBound
THEN {
np: REF Pair ~ NEW[Pair ¬ [low: rp.low, high: lBound]];
process ¬ FORK QuickSortComp[np]
};
IF hBound<rp.high
THEN {
rp.low ¬ hBound;
QuickSortComp[rp];
};
IF process#NIL THEN TRUSTED{[] ¬ JOIN process};
};
QuickSortOptimum2:
PROC [low, high:
INT] = {
process: PROCESS ¬ NIL;
lBound, hBound: Value;
[lBound, hBound] ¬ Partition[low, high];
IF low<lBound
THEN {
process ¬ FORK QuickSort1[low, lBound]
};
IF hBound<high THEN QuickSort1[hBound, high];
IF process#NIL THEN TRUSTED{[] ¬ JOIN process};
};
SortCommand1: Commander.CommandProc = {
SetUp[];
QuickSort1[0, size-1];
Report[cmd.out, "Sort1"];
};
SortCommandComp: Commander.CommandProc = {
SetUp[];
QuickSortComp[NEW[Pair ¬ [low: 0, high: size-1]]];
Report[cmd.out, "SortComp"];
};
SortCommandFORK: Commander.CommandProc = {
SetUp[];
QuickSortFORK[NEW[Pair ¬ [low: 0, high: size-1]]];
Report[cmd.out, "SortFORK"];
};
SortCommandForkOps: Commander.CommandProc = {
SetUp[];
QuickSortFork[NEW[Pair ¬ [low: 0, high: size-1]]];
Report[cmd.out, "SortForkOps"];
};
SortCommandWorker2: Commander.CommandProc = {
SetUp[];
QuickSortWorkerBase[2];
Report[cmd.out, "SortWorker2"];
};
SortCommandWorker8: Commander.CommandProc = {
SetUp[];
QuickSortWorkerBase[8];
Report[cmd.out, "SortWorker8"];
};
SortCommandOptimum2Comp: Commander.CommandProc = {
SetUp[];
QuickSortOptimum2Comp[NEW[Pair ¬ [low: 0, high: size-1]]];
Report[cmd.out, "SortOptimum2Comp"];
};
SortCommandOptimum2: Commander.CommandProc = {
SetUp[];
QuickSortOptimum2[low: 0, high: size-1];
Report[cmd.out, "SortOptimum2"];
};
FreeCommand: Commander.CommandProc = {
Usefull to free array before running another instance of this program
array ¬ NIL
};
SetSizeCommand: Commander.CommandProc = {
i: INT ¬ Convert.IntFromRope[CommanderOps.NextArgument[cmd]];
IF i>0 THEN size ¬ MIN[i, maxSize] ELSE size ¬ defaultSize;
IO.PutF1[cmd.out, "Array size set to %g\n", IO.int[size]];
};
SetSeedCommand: Commander.CommandProc = {
i: INT ¬ Convert.IntFromRope[CommanderOps.NextArgument[cmd]];
IF i<0 THEN seed ¬ constantSeed ELSE seed ¬ i;
IF i=0
THEN IO.PutRope[cmd.out, "Seed set to enforce balanced setup\n"]
ELSE IO.PutF1[cmd.out, "Seed set to %g\n", IO.int[seed]];
};
SetSimpleSizeLimitCommand: Commander.CommandProc = {
i: INT ¬ Convert.IntFromRope[CommanderOps.NextArgument[cmd]];
IF i<0 THEN simpleSizeLimit ¬ 8 ELSE simpleSizeLimit ¬ MAX[i, 3];
IO.PutF1[cmd.out, "SimpleSortLimit set to %g\n", IO.int[simpleSizeLimit]];
};
SetForkSizeLimitCommand: Commander.CommandProc = {
i: INT ¬ Convert.IntFromRope[CommanderOps.NextArgument[cmd]];
forkSizeLimit ¬ i;
IO.PutF1[cmd.out, "ForkSizeLimit set to %g\n", IO.int[forkSizeLimit]];
};
SetChainLengthCommand: Commander.CommandProc = {
i: INT ¬ Convert.IntFromRope[CommanderOps.NextArgument[cmd]];
chainCnt ¬ i;
IO.PutF1[cmd.out, "Chain length set to %g\n", IO.int[chainCnt]];
};
TestOrdering:
PROC [] = {
val: INT ¬ INT.FIRST;
IF array=
NIL
THEN {
ERROR CommanderOps.Failed["Array is NIL\n"];
};
FOR i:
INT
IN [0..size)
DO
IF val>array[i]
THEN {
ERROR CommanderOps.Failed[IO.PutFR1["Failed at position %g\n", IO.int[i]]];
};
val ¬ array[i]
ENDLOOP;
};
CheckCommand: Commander.CommandProc = {
TestOrdering[];
IO.PutRope[cmd.out, "array is sorted\n"]
};
PrintParametersCommand: Commander.CommandProc = {
IO.PutRope[cmd.out, "ForkPerfTest version June 8, 1993\n"];
IO.PutRope[cmd.out, " last change: added MultiChained forks%\n"];
IO.PutF1[cmd.out, "Array size: %g\n", IO.int[size]];
IO.PutF1[cmd.out, "ForkSizeLimit: %g\n", IO.int[forkSizeLimit]];
IO.PutF1[cmd.out, "SimpleSizeLimit: %g\n", IO.int[simpleSizeLimit]];
IF seed =0
THEN IO.PutRope[cmd.out, "Seed: 0 to enforce balanced setup\n"]
ELSE IO.PutF1[cmd.out, "Seed: %g\n", IO.int[seed]];
IO.PutF1[cmd.out, "Chain length: %g\n", IO.int[chainCnt]];
};
chainCnt: INT ¬ 1000;
ChainedFORK:
PROC [x:
REF
ANY ¬
NIL] = {
counter: REF Pair ~ NARROW[x];
p: INT ¬ counter.high MOD 100;
CountFork[counterLock];
IF counter.high>0
THEN
TRUSTED {
counter.high ¬ counter.high-1;
FOR i: INT IN [0..20) DO array[i*p] ¬ i ENDLOOP;
Process.Detach[FORK ChainedFORK[counter] ];
FOR i: INT IN [0..20) DO array[i*p] ¬ i ENDLOOP;
}
ELSE SetDone[counter]
};
ChainedForkOps:
PROC [x:
REF
ANY ¬
NIL] = {
counter: REF Pair ~ NARROW[x];
p: INT ¬ counter.high MOD 100;
CountFork[counterLock];
IF counter.high>0
THEN
TRUSTED {
counter.high ¬ counter.high-1;
FOR i: INT IN [0..20) DO array[i*p] ¬ i ENDLOOP;
ForkOps.Fork[ChainedForkOps, counter];
FOR i: INT IN [0..20) DO array[i*p] ¬ i ENDLOOP;
}
ELSE SetDone[counter]
};
ChainedForkOpsCommand: Commander.CommandProc = {
chainPair: REF Pair ¬ NEW[Pair];
chainPair.high ¬ chainCnt;
SetUp[TRUE];
ChainedForkOps[chainPair];
WaitDone[chainPair];
Report[cmd.out, "ChainedForkOps", TRUE];
};
ChainedFORKCommand: Commander.CommandProc = {
chainPair: REF Pair ¬ NEW[Pair];
chainPair.high ¬ chainCnt;
SetUp[TRUE];
ChainedFORK[chainPair];
WaitDone[chainPair];
Report[cmd.out, "ChainedFORK", TRUE];
};
MultiChainedFORKCommand: Commander.CommandProc = {
chainPair1: REF Pair ¬ NEW[Pair];
chainPair2: REF Pair ¬ NEW[Pair];
chainPair1.high ¬ chainCnt/2;
chainPair2.high ¬ chainCnt/2;
SetUp[TRUE];
ForkOps.Fork[ChainedFORK, chainPair1];
ForkOps.Fork[ChainedFORK, chainPair2];
WaitDone[chainPair1];
WaitDone[chainPair2];
Report[cmd.out, "Multiple ChainedFORK", TRUE];
};
MultiChainedForkOpsCommand: Commander.CommandProc = {
chainPair1: REF Pair ¬ NEW[Pair];
chainPair2: REF Pair ¬ NEW[Pair];
chainPair1.high ¬ chainCnt/2;
chainPair2.high ¬ chainCnt/2;
SetUp[TRUE];
ForkOps.Fork[ChainedForkOps, chainPair1];
ForkOps.Fork[ChainedForkOps, chainPair2];
WaitDone[chainPair1];
WaitDone[chainPair2];
Report[cmd.out, "Multiple ChainedForkOps", TRUE];
};
Actual Measurements
Commander.Register["ForkPerfTest-Sort1", SortCommand1, "Sequential"];
Commander.Register["ForkPerfTest-SortComp", SortCommandComp, "Sequential; use NEW for compensation"];
Commander.Register["ForkPerfTest-SortFORK", SortCommandFORK, "use FORK; MAY WEDGE"];
Commander.Register["ForkPerfTest-SortForkOps", SortCommandForkOps, "use ForkOps.Fork; MAY WEDGE"];
Commander.Register["ForkPerfTest-SortWorker2", SortCommandWorker2, "Worker-Threads 2%"];
Commander.Register["ForkPerfTest-SortWorker8", SortCommandWorker8, "Worker-Threads 8%"];
Commander.Register["ForkPerfTest-SortOptimum2", SortCommandOptimum2, "Optimal 2 threads"];
Commander.Register["ForkPerfTest-SortOptimum2Comp", SortCommandOptimum2Comp, "Optimal 2 threads, NEW for compensation"];
Commander.Register["ForkPerfTest-ChainedFORK", ChainedFORKCommand, "Basicly sequential FORK's"];
Commander.Register["ForkPerfTest-ChainedForkOps", ChainedForkOpsCommand, "Basicly sequential ForkOps.Fork"];
Commander.Register["ForkPerfTest-MultiChainedForkOps", MultiChainedForkOpsCommand, "2 Chains of sequential ForkOps.Fork"];
Commander.Register["ForkPerfTest-MultiChainedFORK", MultiChainedFORKCommand, "2 Chains of sequential FORK's"];
Setup
Commander.Register["ForkPerfTest-Check", CheckCommand, "Test sortedness of array"];
Commander.Register["ForkPerfTest-Parameters", PrintParametersCommand, "Print setup parameters"];
Commander.Register["ForkPerfTest-SetSize", SetSizeCommand, "Set size of array to be sorted"];
Commander.Register["ForkPerfTest-SetSeed", SetSeedCommand, "Set seed for random numbers"];
Commander.Register["ForkPerfTest-SetSimpleSizeLimit", SetSimpleSizeLimitCommand, "Set size for switch to simpler sort"];
Commander.Register["ForkPerfTest-SetForkSizeLimit", SetForkSizeLimitCommand, "Set size for inhibiting forks; MAY CAUSE WEDGE if too small"];
Commander.Register["ForkPerfTest-SetChainLength", SetChainLengthCommand, "Set number for chained operations"];
Commander.Register["ForkPerfTest-Free", FreeCommand, "Free array"];
END.