| Title of proposed project: | Architectural synthesis of computer systems with testability issues |
| Major field of science: | Technical Science |
| Research area: | Computer Structures, Systems, and Networks |
| Duration of project: | 3 years (1995-97) |
| Total work load in hours: | 3.636 |
| Principal investigator: | Dr. Jurij Silc |
| Project summary: | In the research project we will focus on the following topics: how to consider all the relevant factors, costs, constraints, and objectives during the architectural synthesis; how to decide for a given application the number and types of processors to be included in the system; how to decide the interconnection between the selected processors; how to use the designed system effectively to perform the application task; how to map and schedule the subtasks onto the processors; and how to incorporate testability considerations in the architectural synthesis. |
I. The need for design automation on higher abstraction levels
In the computer system design, automated synthesis techniques should be employed
at all stages of the design process. In this way, design cycles would be
significantly reduced, and several different design styles can be generated
and evaluated quickly. In addition, automation may out-perform average human
designers in generating high quality designs. However, due to their
complexity, the present day computer systems are very difficult to design by
handcrafting.
As the complexity of the systems increase, so will the need for
design automation on more abstract levels where functionality and tradeoffs
are easier to understand.
II. Levels of abstraction
The synthesis task is to take a specification of the behavior
required of a system and a set of goals and constraints to be satisfied, and
to find a structure that implements the behavior while satisfying the goals
and constraints.
Just as design is described at various levels of detail, so synthesis
can take place at various levels of abstraction. At the bottom of this
hierarchy is the device level, where the focus is on the internal structure
and behavior of the devices (e.g. transistors). Above this level is the
circuit level, which views the system in terms of the individual
devices. Next comes the logic level, where the system is described as
a network of logic elements (e.g. gates, flip-flops) and the behavior is
specified by logic equations. When the system is viewed as a set of
interconnected storage elements and functional blocks (e.g. registers,
ALUs, Muxes, bus) we have the register-transfer level (RTL). In this case the
behavior is described as a series of data transfers and transformations
between storage elements. Above this level is the algorithmic level, where the
focus is on the computations performed by an individual processor, i.e. on the
way that sequences of inputs are mapped to sequences of outputs.
Finally, at the top of this hierarchy, is the system level. Here,
systems are described as interconnected sets of processors, memories, and
switches.
III. Architectural synthesis with testability issues
The synthesis on the system level is called architectural synthesis.
System-level issues relate to the number and configuration of system-level
components (processors, memories, switches), rather than to how those
individual pieces are designed. For example, the following are also
system-level issues: trading off the complexity between control and data
paths, partitioning the control, breaking a system into interacting
asynchronous processes, breaking a memory array into separate modules,
collecting a set of registers into register file, and changing the bitwidth of
the datapath in order to increase/decrease parallelism.
To date, architectural synthesis aids are not yet commercially available
but the situation is expected to change in the next years opening a
flourishing research and development area.
Some behaviour synthesis efforts has been reported in working prototypes
which may be currently in the transfer phase to the industry.
The following topics of current research in high level synthesis will be
studied in our proposed basic research project:
1.) how to consider all the relevant factors, costs, constraints,
and objectives during the architectural synthesis,
2.) how to decide the number and types of processors
to be included in the system,
3.) how to decide the interconnection between the
selected processors,
4.) how to use the designed system effectively to
perform a given application task,
5.) how to map and schedule the subtasks onto the processors, and
6.) how to incorporate testability considerations in
the architectural synthesis.
I. State of the art in the high-level synthesis
The roots of high-level synthesis can be traced back to the 1960s.
During the 1970s most of the effort went into automating tasks at lower
levels of the design hierarchy, such as layout.
In addition, great progress
was made in the development of techniques and algorithms. In the 1980s work
on high-level synthesis started to spread from the academic community to
industry. Nowadays, high-level synthesis systems are producing manufacturable chip
designs for applications such as signal processing, pipelined processors,
and interfaces.
It is expected that architectural synthesis aids will become commercially
available as a result of the flourishing research and development in this
area of the high-level synthesis (Lagnese and Thomas, 1989; Gajski et al., 1994).
The modern synthesis approach can be described as follows. The structural
description of a system is a specification of a set of components and their
interconnections. More recently, however,
behavioral descriptions of systems are used. Such a description
specifies what the system needs to do, i.e. the way that each of the
components interacts with its environment.
High-level synthesis transforms behavioral description to the
structural one. A typical way of describing behavior is to write a program
in an ordinary computer language or in a special hardware description
language (e.g. VHDL).
The first step in high-level synthesis is usually the compilation of the
hardware description language into an internal representation. Most
approaches use flow graphs to represent both the
data flow and the control flow implied by the specification.
Before proceeding to the second
step it is desirable to do some initial optimization of the flow graph, such
as a dead code elimination, constant propagation, common subexpression
elimination, and loop unrolling.
The second step of the high-level synthesis, which is the core of
transforming behavior into structure, includes operation scheduling
and hardware allocation. These two tasks have been studied extensively and a
variety of algorithms have been published by Silc and Robic, 1993;
Silc, 1994a; and Silc, 1994b.
Overviews of the different
schools of thought have been given by McFarland et al., 1990;
and Gajski et al., 1993. The scheduling and
allocation are closely interrelated. In order to have an optimal design,
both tasks should be performed simultaneously. However, due to the
time complexity, many systems perform them separately
or introduce iteration loops
between the two subtasks. Scheduling involves
assigning the operation to control steps which are
the fundamental sequencing units in synchronous systems.
Allocation involves assigning the
operations and values to hardware, i.e., providing storage, function units,
and communication paths, and specifying their usage. To minimize them
together is usually too complex, so in many high-level synthesis systems they
are minimized separately. Therefore, allocation is usually further divided
into three subtasks -- variable binding, operation assignment,
and data transfer binding. Variable binding refers to the allocation of
registers to data, i.e., values that are generated in one control step and
used in another must be assigned to registers. Some systems have a one-to-one
correspondence between variables and registers, while others
allow register sharing for those variables which have disjoint lifetimes.
Operation assignment binds operations (e.g., addition)
to function units (e.g., an adder or an ALU). Of course, operations can share
functional units only if they are mutually exclusive, that is, they are
assigned to different control steps.
The problem is then to form the minimum
number of groups consisting of mutually exclusive operations since this will
minimize the number of function units.
Data transfer bindings represent the
allocation of connections (e.g., busses, multiplexers) between hardware
components (i.e., registers and function units) to create the necessary
information paths as required by the specification and the schedule.
Connections consist of busses and/or multiplexers. Busses offer the advantage
of requiring less wiring, but they may be slower than multiplexers. A
combination of both is often the best solution.
Once the schedule and allocation have been accomplished, it is necessary to
synthesize a controller (hardwired or microcoded) that will drive
allocated resources as required by the schedule. Finally, the design has to
be converted into real hardware. Lower level tools such as logic
synthesis and layout synthesis complete the design.
While the high level synthesis is naturally a top-down process,
testing and conventional design-for-testability (DFT) techniques are mainly
bottom-up activities. DFT rules are typically applied after the RTL structure
of a circuit has been defined. To bridge the gap between the state-of-the-art
in design synthesis and in test synthesis, high level DFT principles are
now intensively investigated. The research is oriented toward multi-criterion
decision analysis of design controllability/observability, minimization
of self-loops, and integration of off-line and on-line self-testing
structures.
II. Future of high-level synthesis
There are still many unanswered questions related to such issues as
specification, input/output, designer intervention, complex timing
constraints, and the relation of synthesis to the overall design and
fabrication process.
There is an acute need for theoretical formulation of high-level
synthesis problems, development of canonical forms, and optimization
algorithms for different application architectures (Gajski et al.,
1994). In order to move
upwards effectively, we need to build other description languages on
top of the popular VHDL. Additional work is needed on more general
representations of algorithms and design styles for high-level synthesis.
Research is also needed for taxonomize target architectures and provide
modeling guidelines for different abstraction levels for each target
architecture. More comparative work is needed to establish good
quality-measures and good estimation algorithms for quality-measures that
can quickly reduce the search through the design space. Since most
algorithms make oversimplified assumptions regarding target architectures,
more work is needed on algorithms for more realistic design models. There is
a lack of standard component sets for high-level synthesis and
algorithms for technology mapping between arbitrary component sets.
Technology mapping should be extended to higher-level system components,
which in turn will require proper formalization of component descriptions.
The success of high-level synthesis depends on a good support framework,
including databases, environments and graphical front-end, to sustain
system design at higher levels. Research on databases is sporadic and
work on environments is almost nonexistent.
Initial results in high-level DFT that have been reported recently
indicate that algorithms that focus on single design issues (i.e.,
bracking or reducing self-loops) are relatively simple (Steensma et al.,
1993; Eschermann, 1993; Mujumdar et al., 1994).
However, much
more effort will be required for multi-criterion
decision analysis of design controllability/observability and
incorporating of self-testing structure. An interesting issue
is also the relationship between 1149.* DFT standards that are currently
under development and the high-level DFT techniques in order to effectively
use the advantages of both sides.
These are some of the areas where much work and development are needed in
order to make high-level synthesis practical.
S.Raman, L.M.Patnaik, J.Silc, and M.Spegel.
Parallel Implementation of VLSI Circuit Simulation.
Informatica 15 (1991)
B.Robic, P.Kolbezen, and J.Silc.
Area optimization of dataflow-graph mappings.
Parallel Computing 18 (1992)
J.Silc, B.Robic.
Program partitioning for a control/data driven computer.
J. Computing and Information Technology 1 (1993)
B.Robic, J.Silc.
High-performance computing on a honeycomb architecture.
Lecture Notes in Computer Science 734 (1993)
F.Novak, N.Sutanovac, R.Trobec.
Built-in self testing of communications systems using ASIC technology.
Microprocessors and Microsystems 17 (1993)
F.Novak, I.Mozetic, M.Santo-Zarnik, A.Biasizzo.
Enhancing design-for-test for active analog filters using CLP(R).
Analog Integrated Circuits and Signal Processing 4 (1993)
also in J. of Electronic Testing: Theory and Applications 4
(1993)
J.Silc.
Scheduling strategies in high-level synthesis.
Informatica 18 (1994)
J.Silc.
Scheduling and allocation in high-level synthesis.
Operations Research '93 (Physica-Verlag, 1994)
E.D.Lagnese, D.E.Thomas.
Architectural partitioning for system level design.
Proc. 26th DAC (1989)
M.C.McFarland et al.
The high-level synthesis of digital systems.
Proc. IEEE 78 (1990)
D.D.Gajski et al.
High-level synthesis: Introduction to chip and system design.
(Kluwer Academic Publishers, 1993)
J.Steensma, W.Geurts, F.Catthoor, H. De Man.
Testability Analysis in High Level Data Path Synthesis.
J. of Electronic Testing: Theory and Applications 4 (1993)
B.Eschermann.
Enhancing On-Line Testability During Synthesis.
J. of Electronic Testing: Theory and Applications 4 (1993)
D.D.Gajski et al.
System level methodology and technology (Tutorial).
Proc. Europ. Design and Test Conf. (1994)
A.Mujumdar, R.Jain, K.Saluja.
Incorporating Testability Considerations in High-Level Synthesis.
J. of Electronic Testing: Theory and Applications 5 (1994)
It is the fact that very little has been done to provide architectural
synthesis aids. However, it is expected that automated synthesis techniques,
when developed and applied at the system level, can:
The significance of the results is that, given the behavioral description of an application, we will have the ability of generating, evaluating and selecting candidate computer system designs at the system level. Here, several far-reaching decisions have to be made regarding the number and types of processors, interconnection structure, mapping and scheduling the subtasks, and systematic introduction of testability into the system.
Since the present day computer systems become more and more difficult to design by using ad hoc techniques, the techniques of the architectural synthesis are more and more needed, as they promise shorter design cycles and offer several design styles for a given application. A good automated architectural synthesis (together with syntheses on lower levels) may out-perform average human designers in generating high quality designs.
The first period of the project will deal primarily with the relevant factors, costs, constraints, and objectives of the architectural synthesis. Clarification and sistematization of these issues is neccessary from the methodological standpoint of view since architectural synthesis is a new research field. These issues will subsequently be used to conduct search methods in the architectural design space. Several (heuristic) search methods will be evaluated. Also, the design space will be defined by specifying, for each architecture, the attributes such as the number and types of processors, the interconnection topology, amenability for supporting the application of a given type and the introduction of the testability, etc. The core of the synthesis consists of the partitioning, scheduling, and allocation of the subtasks to the processors of the selected system architecture. Being NP-complete, the problems are usually tackled by heuristic methods. Several of these methods will be evaluated and their applicability will be determined for a given architecture and application type. The objective is to use the designed system effectively to perform a given application task. Current trends in incorporating testability considerations in high level synthesis will be studied and papers and reports of applications will be surveyed. Emphasis will be given to the problem of effective cooperation of high level DFT techniques and the conventional bottom-up DFT solutions defined by the emerging IEEE 1149.* standards. For this purpose, test propagation through modules and circuits for hierarchical test generation, based on ambiguity set algebra, will be studied. Case studies will be performed on currenty available design tools (Alliance, Ocean) possibly upgraded by some public domain architectural synthesis tool.
In the first year of the project we will address the problem of defining, analyzing, and systhematizing the relevant factors, such as costs, constraints, and objectives of the architectural synthesis. We will define the design space and specify, for each architecture, the relevant atributes including the number and types of processors, the interconnection topology, the amenability for supporting the application of a given type and introduction of the testability, etc. The research of the design for testability in high-level synthesis will deal with the analysis of selected testability techniques which are likely to be applied in later synthesis. In particular, the notion of C-testability and the related implementations of C-testable structures, BILBO methodology and the corresponding families of testable designs, and other existing on-line checking and off-line BIST techniques will be studied. Besides, recent papers in the design for testability in high level synthesis will be studied to learn the state-of-the-art of the problem solutions and to identify the main directions of further work. Possibility of upgrading existing design software by high level synthesis tool will be explored. As a result, a survey of the background will be produced.
During the second year of the project we will evaluate several heuristic methods to conduct the search through the architectural design space. We will evaluate the possibility to fully automate the search and decision making, and spot the problems which call for human intervention. The work on synthesis of the above DFT techniques in the context of test propagation through modules and circuits and the related ambiguity set algebra is envisaged.
In the third year, we addres the problem of effective use of the selected system design. To do this, we will consider the problems of efficient partitioning, scheduling, and allocation of the subtasks of the application to the processors of the selected system architecture. We will analyze several heuristic methods and evaluate their applicability for a given architecture and application type. Emphasis will be given to experimental case studies. Trade-off in the relationship between top-down and bottom-up design for testability approach will be considered in the proposed solutions.