abstraction, where unit-time instructions execute one at a time.
The rudimentary parallel abstraction I propose here is that indefinitely
many instructions available for concurrent execution execute immediately, dubbing the abstraction Immediate
Concurrent Execution. A consequence
of ICE is a step-by-step (inductive) explication of the instructions available
next for concurrent execution. The
number of instructions in each step is
independent of the number of processors, which are not even mentioned.
The explication falls back on the serial
abstraction in the event of one instruction per step. The right side of Figure 1
outlines parallel execution as implied
by the ICE abstraction. At each time
unit, any number of unit-time instructions that can execute concurrently do
so, followed by yet another time unit
in which the same execution pattern
repeats, and so on, as long as the program is running.
How might parallelism be advantageous for performance? The PRAM
answer is that in a serial program the
number of time units, or “depth,” is
the same as the algorithm’s total number of operations, or “work,” while in
the parallel program the number of
time units can be much lower. For a
parallel program, the objective is that
its work does not much exceed that
of its serial counterpart for the same
problem, and its depth is much lower
than its work. (Later in the article, I
note the straightforward connection
between ICE and the rich PRAM algorithmic theory and that ICE is nothing
more than a subset of the work-depth
model.) But how would a system designer go about building a computer
system that realizes the promise of
ease of programming and strong performance?
Outlining a comprehensive solution, I discuss basic tension between
the PRAM abstraction and hardware
implementation and a workflow that
goes through ICE and PRAM-related
abstractions for programming the
XMT computer architecture.
Some many-core architectures are
likely to become mainstream, mean-
ing they must be easy enough to pro-
gram by every CS major and graduate.
I am not aware of other many-core
architectures with PRAM-like abstrac-
tion. Allowing programmers to view a
computer operation as a PRAM would
make it easy to program, 10 hence this
article should interest all such majors
figure 1. serial execution based on the serial ise abstraction vs. parallel execution based
on the parallel ice abstraction.
(Immediate serial execution)
Natural (parallel) algorithm
(Immediate concurent execution)
Time = Number of Operations
Time << Number of Operations