¿ìè¶ÌÊÓƵ

PARALLELISM and computing have never been comfortable together. The
idea of running many processors in parallel to speed up computers, rather
than using a single processor that does one operation after another, in
sequence, has been around for at least 40 years. But the lack of cheap,
reliable processors and programmers’ reluctance to learn how to program
in parallel have hindered the development of parallel computing. Over the
past year, however, the parallel approach has established itself as the
only way to make computers fast enough and powerful enough to satisfy the
demands of scientists and engineers.

Two large and interconnected problems stand in the way. First, there
is little standard software to simplify the job of writing programs for
parallel computers. Secondly, the hardware of parallel computers differs
from machine to machine. As a result, scientists often have to program a
parallel machine in the manufacturer’s own language, or an extension of
a language developed for sequential computers. Parallelism that is flexible
enough to handle complex scientific problems and accessible to anyone is
still out of reach. Over the next five years computer designers must create
‘general-purpose’ parallel computers if they are to realise the promises
of parallel processing. Opinions differ on what such parallel hardware should
look like, but it is likely to be a hybrid of the existing, specialised
parallel computers.

Parallel computing relies on an array of processors, commonly arranged
in a fixed two-dimensional grid, or as a stack of cubes, known as a hypercube.
The processors exchange messages so that they can all work on a problem
at once. Two main schools of parallelism have grown up around the two most
popular types of parallel computer. One is the SIMD (single-instruction
multiple-data) computer, where the processors each carry out the same operation
on many pieces of data at the same time. The Distributed Array Processor
designed by ICL in Britain in the late 1970s, and the Connection Machine,
developed by Thinking Machines in the US, are SIMD computers: they are particularly
good at image processing, for instance, where fragments of a picture are
analysed in the same way simultaneously. In MIMD (multiple-instruction multiple-data)
computers, however, the processors carry out different operations at the
same time. They are better at solving problems that require each processor
to execute its own program on its own data, communicating periodically with
its neighbours. There are two main types of MIMD computers: in one, processors
have individual memories; in the other, processors share a memory. The way
the processors communicate also varies. Some computers have fixed links
between their processors; in others, the links can be adjusted to suit a
particular problem.

In conventional computing, software written for one sequential machine
can run on any other sequential machine with relative ease: this is known
as ‘software portability’ and it has helped to make conventional computing
widely accessible. In parallel processing, software designed for one machine
cannot run on another without sacrificing some of the increase in power
and speed that parallelism offers. David May, a leading protagonist of parallel
processing, sees the development of a general-purpose parallel computer
as the only way round this limit to software portability. He is one of the
founders of Inmos, the company that developed the transputer, a parallel
processing chip, and the programming language, occam, to exploit it.

In his search for a standardised parallel computer, May draws an analogy
between the development of parallel computing and that of conventional computing.
In the early days of sequential computing, the style of programming was
dictated by the hardware, which often varied from machine to machine. For
instance, some early computers relied on memory held on a drum. Programmers
retrieved data from these memories by waiting for the drum to revolve in
order to find the right piece of data to feed into each part of their program.
They had to ensure the data associated with each instruction were in the
right place at the right time, allocate pieces of data to different drums
and direct the program to the correct drum to find the data it needed. Parallel
processing faces a similar problem today: the hardware is dictating the
way programmers work – and they don’t like it.

In sequential computing, two things freed programmers from having to
tell their computers how and where to store data. First, programmers developed
clever software that hid the details of the way the processors operate,
effectively automating the programming process; secondly, hardware designers
rearranged the processing units and memories so the computer became easier
to program. All this involved developing ‘compilers’, programs that convert
the instructions from a programmer into a form that any machine can run
as long as it is programmed to understand the compiler. Compilers protect
programmers from the details of the hardware of sequential computers; they
allow programmers to deal with idealised, or ‘abstract’, machines. An abstract
machine does not exist; it represents the real hardware in the same way
as the map of the London underground does not show the exact detail of each
line but helps passengers to travel round the city. Secondly, designers
of the hardware helped programmers by developing machines with memories
arranged so that one piece of information is as easy to retrieve as another;
these are so-called ‘random-access’ machines.

Programmers of parallel machines have had to get used to programming
the hardware of their parallel computers without any intermediaries, writing
in a language that their machines ‘think’ in; the equivalent of compilers
for parallel machines are only now being developed. Last month Meiko, a
British company that builds supercomputers, began to sell software designed
to make parallel programming easier. CS (Communicating Sequential) Tools
allows programmers to develop new software and to adapt their existing sequential
programs for parallel computers. It cushions programmers from the details
of the hardware they use and lets them write an entire parallel program
on a standard workstation. They can then run these programs either on an
array of transputers or on a network of workstations working in parallel.
At present there is a limit to the hardware on which they can run their
parallel program; but the advantage of CS Tools is that programmers do not
get bogged down in telling the processors exactly how they should communicate.

The Meiko software adopts an equivalent role in parallel processing
to that of compilers in sequential computers; it shows programmers only
an abstract version of the hardware. Programmers write their software in
a sequential language they know well, such as C or Fortran, and CS Tools
allows it to run in parallel. They split a problem into a set of sequential
programs and tell CS Tools which processes are to be used in their piece
of software, where they want these processes to run and which need to communicate.
In most cases some of the processes, such as displaying information on the
screen or extracting data from a store in the computer, will need services
that a conventional machine provides using a form of housekeeping software,
known as the operating system. CS Tools intercepts the requests for such
services and passes them to the conventional operating system on the host
machine.

Searching for software cushions

Research groups around the world are working on similar cushioning software
for nearly all multiprocessor machines. At the California Institute of Technology,
Pasadena, one group has developed the Crystalline Operating System (CrOS),
an operating system for parallel computers whose processors are arranged
in a hypercube. A descendant of the CrOS software, known as Express, is
now available from an American company called Parasoft. A similar operating
system, called Trollius, first developed by Cornell University in New York
State, is now being sold by a company called Ohio Supercomputer. At the
University of Edinburgh, another team is working both with Distributed Array
Processors in a SIMD computer, and with an array of 500 transputers in a
MIMD machine. The researchers aim to produce software to help to solve problems
that involve large and complex calculations, such as finite element analysis
and simulation programs in theoretical physics.

Without such cushioning software, programmers have three options if
they want to write a parallel program. They can learn to use a parallel
language, such as occam, and write their programs with it. They can write
a harness, or shell, in occam and run their existing sequential code as
subroutines, which the shell calls up as if they were part of the main program
(‘Supercomputers and the need for speed’, ¿ìè¶ÌÊÓƵ, 12 November 1988).
Or they can use parallelising compilers to translate their sequential code
line by line so that it will run on parallel hardware, but these compilers
are in their infancy.

This month a European partnership starts a four-year project to produce
a compiler that will automatically translate code written in Fortran for
use on parallel hardware. The project, called Supernode II, also aims to
develop operating systems for parallel hardware, and software to simplify
the programming job. Another important goal of Supernode II is the creation
of a library of parallel software that can solve common numeric routines,
such as linear algebra and matrix arithmetic. The team is working with the
Numerical Algorithms Group, a company based in Oxford, which already provides
a large library of commonly used software for sequential computers. The
project involves Thorn EMI, which sold Inmos to the Italian-French company
SGS-Thomson earlier this year, and nine other partners.

CS Tools and the work at Caltech and Edinburgh will undoubtedly bring
great benefits for people who want parallelism now, but all of these approaches
tackle the difficulty of programming parallel computers by using software
alone. May, of Inmos, sees far greater prizes for parallel computing if
machine designers could take the same logical step that produced machines
with random-access memories in sequential computing. This would free programmers
from writing software that has to be carefully matched to the structure
of one computer, and it would make far more efficient use of parallelism.
May believes that people pay a price in terms of performance if they use
software aids alone to ease the programming of parallel machines. The time
it takes to send messages through these software cushions limits the performance
you obtain from a parallel machine. For instance, if a message takes 100
microseconds to pass between processors, the programmer must give each one
a large enough problem to keep it busy for at least 100 microseconds, while
it waits for its next message. This limits the number of chunks into which
you can break down a problem, and hence the degree of parallelism you can
use to attack that problem. In May’s vision of a general-purpose parallel
machine, software such as CS Tools that automatically sends messages to
the right place, would be replaced by automatic hardware switches to route
messages. This would reduce the time it takes to send messages and allow
programmers to get the best out of parallel computing.

Designers of computers are beginning to consider what they can do to
help. Over the next few years, May expects each one to develop its own ‘standard’
hardware. ‘Such machines would be sufficiently similar that a new compiler
could take software and run it on any parallel computer,’ he said. This
would bring enormous benefits to scientists. They would no longer have to
program a parallel computer afresh every time they want to solve a more
complex problem; they could simply re-use old software, even if it was written
for a different parallel machine.

The development of common hardware would also encourage more people
to write libraries of standard software, similar to those that now exist
for sequential machines. A team of scientists from NASA and Lockheed is
developing a robot called EVA, the Extra Vehicular Activity retriever robot,
to work outside the space station promised by the end of the century. Keith
Graham, who is working on the project, says that his team could have cut
its workload by one-third if standard software for parallel hardware were
available: instead it had to write its own programs from scratch. Transputers
control the robot, which ‘sees’ using lasers and a video camera, and has
two arms and a three-fingered hand. An array of five transputers controls
the image-recognition system, makes sense of the images it picks up and
tells the robot what to do next. A smaller array directs the propulsion
unit while a single transputer controls the collection of gyroscopes that
monitor the robot’s movements.

A dearth of standard software for parallel computers is not the only
result of the lack of common, general-purpose hardware. This has also restricted
the way people program parallel machines. According to May: ‘There will
always be some people who are prepared to design their own special-purpose
parallel machines and programs, but the problem is that when programmers
have always to match their software to the underlying hardware they end
up cramping their programming style.’ Programmers have developed different
ways of programming parallel systems. They might ‘farm’ a problem to a number
of processors on an array and use another processor to control them; or
‘pipeline’ a piece of data through a series of processors, each carrying
out a different process; or break up a problem geometrically and match a
portion to every processor in an array, which is a useful approach for processing
an image.

Even so, some problems are best handled by algorithms that include a
mixture of all three. Software developers are now agreed that writing a
better algorithm to solve a problem is far more efficient than waiting for
a better technology or manufacturing process to come along to make your
processors smaller and faster. But this relies on a machine whose links
between processors can be altered almost infinitely, in order to cope with
each new algorithm. Thus, the key to making a useful standard parallel computer,
incorporating all three of the most common programming styles, is a very
flexible communications network. According to May, the ideal model would
embrace aspects of both of the two forms of MIMD machines that already exist:
one with common memory accessible to any processor, and the other with processors
with individual memories. Its hardware would have to handle instructions
from the processors whenever they wanted to communicate with any other processor
or with any memory on the network, rather than just their own personal memory.
At the moment, software passes such instructions between processors that
are not next to each other. Future transputers will be able to do this through
their hardware, which will allow them to work very much faster.

All this should make it possible to build a standard, general-purpose
parallel computer. It might be no more powerful than today’s supercomputers
but it would be capable of solving a far wider range of problems quickly
in a parallel fashion, because there would be hardly any limit to the way
that the links between the processors could be arranged. May argues that
the only thing holding up the construction of experimental versions of general-purpose
parallel computers is the availability of cheap components.

There are already signs that different forms of parallel hardware, or
architectures, are merging. Some American chip companies are building processors
for parallel computers that look more like the transputer, which has its
own built-in processor, memory and communications links. Intel, the American
semiconductor giant, recently produced the i860 chip and is thought to be
developing a parallel processing chip, called I-Warp, which imitates the
transputer.

The idea of using a far more flexible network to link the processors
in a parallel computer is also catching on now in the US. In June NCUBE,
an American company that builds parallel processors and supercomputers,
began to sell a new parallel supercomputer that it claims is more powerful
than any existing machine. In two respects the company has already used
May’s ideas for the general-purpose parallel computer. The processors that
make up the hypercube of an NCUBE computer contain the hardware they need
to communicate with each other; furthermore, all the algorithms that govern
the transfer of data have been taken out of software and put into hardware.
The company also stresses the importance of the flexibility in the links
between the processors in achieving the new machine’s very fast processing
speeds. It says that the NCUBE 2 is about 6 to 8 times as fast as the company’s
earlier machines, which were themselves about 10 to 15 times as fast as
the Cray X-MP supercomputer. Compared with the proposed general-purpose
parallel computer, however, the NCUBE machines can solve only a narrow range
of problems. Software companies have already begun to develop products,
similar to CS Tools, to make programming easier on the NCUBE 2 machine.

Those who subscribe to the SIMD school of parallelism are not so convinced
of the need for general-purpose hardware to get the most out of parallel
computing. Geoff Manning, chairman of Active Memory Technology, the British
company that now sells the Distributed Array Processor (DAP), predicts a
bright future for SIMD machines without changing the basic hardware. He
says there are three ways of speeding up the DAP and, within a decade, he
plans to have produced an array that is 1000 times as fast as the very first
DAP array, which was created in the early 1970s. He aims to use more processors
in the array itself, increase the speed of the processors by using gallium
arsenide rather than silicon, and build processors that can handle more
information at a time.

The problem for scientists and engineers eager to process in parallel
is that it is not yet clear whether May’s ‘merged’ parallel hardware, Manning’s
beefed-up arrays, or some mixture of the two is the best way forward. For
even Manning concedes that designers may need to be able to link different
architectures, or to set up giant heterogeneous architectures by building
MIMD machines out of SIMD processors.