The purpose of this thesis was to determine if reconfigurable
logic arrays could be a viable alternative to today's general purpose
processors, tackling the same wide variety of tasks and performing
roughly as well. More than this it was hoped that this thesis could
propose for the first time an architecture based on reconfigurable
logic which satisfied these aims.
This thesis demonstrates that reconfigurable processors
do have the ability to entirely replace conventional
processors. The Switchblade system described is a complete
general-purpose computer based entirely around a reconfigurable logic
array. It lacks only appropriate software to make it a realisable
system.
Von Neumann's sequential model of computing has served us well
for a number of years. Now for the first time there is an opportunity
to pursue an entirely different model based on ultra-fine-grained
parallelism. Research has already shown us that this model offers
performance advantages in some cases. This thesis demonstrates that
an architecture such as Switchblade can perform satisfactorily
even in the types of situations which it is most poorly suited to.
Existing logic array processors are at a relatively early stage of
development as computing devices. A large step is required to take
them from the basic computing devices they are and transform them into
general purpose computing devices. The intent of the
Switchblade project was to make this very step.
Several new architectural features were created to enable the
logic array to function more like a general purpose computer and less
like the custom computing systems that preceded it. The most
important of these features was virtualisation, which
permits a small logic resource to execute disproportionately large
programs. It also abstracts the logic array in a way which allows
programs to be developed independently from concerns about the
physical bounds of the processor. More importantly, it ushers in true
parallel multitasking as a standard feature for the first time on a
logic array processor. With virtualisation and appropriate software
tools it is possible to program and operate Switchblade in
much the same way you would a normal general-purpose computer.
A number of lower-level enhancements were also made to the logic
array, particularly in the area of routing. Special systems for
distributing broadcast signals and multiplexing multiple signals on a
single line improve the density of circuitry on the die. Multiple
configuration stores further increase density, particularly when used
to their maximum in a multi-tasking, multi-user system.
Some important conclusions:
- Multiple configuration stores offer performance and density enhancements
- Maximum benefit from a limited reconfigurable logic device
demands that the available logic be reconfigured to new configurations
frequently. Reconfiguration is inherently slow however so it makes
sense to cache configurations on-chip for fast access. Simulations
have shown multiple configuration stores to be particularly effective in
dealing with the kind of large, hard-to-parallelise program which this
project particularly targets.
- Self-reconfiguration is a powerful optimisation for logic arrays
- Applications can be constructed using self-reconfiguration which
are faster than similar algorithms without self-reconfiguration. The
main restriction to date has been slow reconfiguration interfaces.
Switchblade addresses this issue.
- Abstract machines can be a useful tool in architectural experimentation
- A relatively speculative project like this one faces many
difficulties in the relative immaturity of the infrastructure
available. Despite the fact that the project scope extended only as
far as the architecture of the proposed machine it proved very
difficult to test the architectural ideas without other tools such as
compilers and synthesis software to match the architecture not to
mention an entire operating system which would run on it.
Some tools were created to aid the development of the
architecture, and proved invaluable in testing and refining
architectural features without the support of any real tools. One of
these tools was an abstract machine which permitted the effects of
various architectural features to be gauged without the side-effects
of other architectural assumptions. ``Traits'' provided a way of
measuring the effects of real-life scenarios on this abstract
architecture.
- The dichotomy between sequential and logic approaches is artificial
- The approaches to sequential program construction and logic
circuit construction have traditionally been very different from each
other. Now that devices such as Switchblade bridge this gap
more advanced tools are needed which express algorithms in more
general terms which are equally applicable to either form.
Further than this, it is now clear that there are fine gradations
between the two approaches and most algorithms are best expressed in a
form which falls somewhere between the two. Most current algorithms
are expressed in a form which is biassed toward sequential execution,
so it is not surprising that many performance studies indicate a
preference for conventional processors.
- Programming approaches geared to logic arrays can provide substantial performance improvement
- A number of different approaches to creating algorithms have been
developed which specifically favour logic arrays. It is not clear
whether an existing algorithm can be automatically modified to use
these approaches.
- Self-reconfiguration implies a paradigm shift in how computation can be performed
- Instead of devising algorithms to run on and exploit a given computer
architecture, an architecture is defined dynamically to perform the
computation. While much work is still required the conceptual framework
presented here paves the way for exciting future developments.
- Genetic algorithms can produce effective and unusual architectures
- Using an optimisation approach to obtain the best architecture
rather than ad-hoc design can produce more efficient - and
sometimes surprising - architectures. A genetic algorithm was used aid
to designing the logic array and showed that often asymmetrical
designs offer superior performance to the conventional symmetrical
ones.
- There is no ``one true logic array architecture''
- Experimentation with optimisation methods and a variety of circuit
scenarios demonstrates that different styles of logic array are better
suited to different styles of circuit. There is no obvious logic array
design which is clearly superior to others in a wide range of
applications.
- Multiplexed lines can reduce interconnect costs
- Interconnect is the most expensive resource in logic arrays, yet
most lines have only a fraction of their available bandwidth used.
Multiplexing provides a means of routing multiple lines over
relatively long distances with low die area used.
- Routable broadcast can reduce interconnect costs
- Many signals are used by a number of logic blocks in the same
region, or in the case of master clock signals are used heavily
throughout the array. Special support in Switchblade for a
multiplexed, routable
broadcast system makes this feature cheap and effective.
- Switchblade interconnect has limited speed or range
- A disadvantage to the tradeoffs in Switchblade's design is
that propagation delays are incurred at every logic-cell-width step.
This would make the cost of long lines very high except that these can
be routed using the higher level virtualised routing system. This
system can transmit more efficiently over longer distances.
- Efficient self-reconfiguration is possible
- Most logic arrays which allow run-time reconfiguration provide a
single addressable interface to the configuration store.
Self-reconfiguration from within an array can be more efficiently
achieved using the routable broadcast system. This removes the
single-interface bottleneck of other systems and permits any number of
cells to be reconfigured simultaneously.
- Message passing provides a good fundamental virtualisation transport
- Where MMU lookup tables provide virtualisation for memory, a
different mechanism is required in virtualising logic arrays.
Virtually-addressed message passing provides this mechanism in
Switchblade, changing the logic resource from being static and
limited to a relatively abstract resource which can be allocated on
demand by the operating system.
- Multitasking / multiuser logic array computer systems are possible
- Virtualising the logic resource also makes it easy to run multiple
programs on the system without them having to know about each other.
Whether parts of the programs run in parallel or are task-switched
depends on how easily the operating system can find space for their working sets.
Task switching is fast due to the availability of multiple
configuration stores.
- Security is possible in a multiuser logic array computer system
- Realistic multiuser systems must protect tasks from each other.
Switchblade's password capability addressing system provides a
hardware basis for a more sophisticated operating system security system.
- The operating system is no longer a software product
- Switchblade provides an operating system which is
partially in sequential code, partially in reconfigurable logic,
partially in special hardware and partially in ``extensible operating system
functions'' which are reconfigured add-ons to the existing special
hardware. What's more parts of the operating system may migrate between being
sequential code and logic. The old distinctions between hardware and
software are blurring.
- Sequential execution on logic arrays is not inefficient
- By providing a small amount of special support for sequential
execution units it is possible to implement bit-slice sequential
processors in a compact way. Inherently sequential tasks can then be
executed without wasting precious array space. Even better, the
sequential processors can be customised to the particular application.
- Performance of Switchblade's may be acceptable
- Simulated performance tests of the proposed virtual logic system
indicate that it may well be capable of running even large, complicated,
poorly-parallelised programs
without unacceptable performance degradation. The array
parameters of size and the number of configuration stores proved to
have been well chosen for the simulated system. When performance
degradation occurs it is
relatively graceful and does not result in excessive thrashing.
- General purpose logic array processors are viable
- This is the most important conclusion of the thesis. Logic array
processors are no longer restricted to specialised custom computing
applications - they are just as applicable to general applications
if they have suitable infrastructure. The design presented in
this thesis details a suitable infrastructure.
The Switchblade project was very large in the scope of what
it was attempting to achieve, yet greatly hampered by the limited
resources available to it. For practical reasons it was necessary to
limit the scope of the project to something achievable in the time
frame and as a result many important and interesting areas of research
were glossed over. The focus had to remain on the central goal of
proving the viability of reconfigurable logic arrays as a
general-purpose computing device.
Switchblade has never been implemented in hardware. The
only true test of an architecture is how it works in real life.
Unfortunately a hardware implementation was precluded both on the
grounds of the size of the task and a lack of funding. The obvious
next step would be to take Switchblade or a similar system and
implement it on a die. Fabrication densities high enough to create
complete computer systems based around reconfigurable logic should be
available in the next few years.
The other Achilles heel of the project was the lack of supporting
software tools. Despite making circuit synthesis easier in some ways
through good low-level homogeneity the architecture presents a number
of new problems in circuit synthesis due to its multiplexed routing
system, routable broadcast system and virtualised routing system.
Solving these problems was outside the scope of the thesis and so
remains a research area.
Operating systems for these kinds of computers also remain a
research area. Some hints at the form such an operating system might
take became apparent during the design of Switchblade but the
great bulk of the work remains obscure. It is very well to demonstrate
that general purpose reconfigurable logic array computer systems are
possible, but they cannot become a reality until software tools and
operating systems are developed.
It is quite possible that in future all computers will be based
entirely around reconfigurable logic. Has Von Neumann had his day?
Maybe. Reconfigurable logic certainly offers performance advantages
over conventional processors in some applications, and research is
demonstrating new ways of applying it to an ever-widening variety of
tasks all the time. This thesis adds a new spoke to the wheel of
reconfigurable computing systems - now they can be used as general
purpose processors, not just as specialised custom computing engines.
With this step reconfigurable logic suddenly becomes a serious
challenge to conventional processors.