/ Tuneo Ikedo / Professor
/ Michael Kishinevsky / Professor
/ Robert H. Fujii / Associate Professor
/ A. Y. Kondratyev / Associate Professor
/ Yamin Li / Associate Professor
/ Omar Hammami / Assistant Professor
/ Wanming Chu / Research Associate
Single-chip GVIP This is a joint research project with 5 companies. The development phase is in progress for the software and hardware.
AIZU Supercomputer This project has progressed well in the hardware development phase; the PE board has already been designed and fabricated. Currently, the evaluation and testing phase for the hardware (PCB board, etc.) is under way. Software development is being conducted by the Distributed Parallel Processing Laboratory.
Memory Hierarchy Management Design and development activities related to memory hierarchy management algorithms and multiport hardware continues. Last year's results have been improved with linear space algorithms. Attempts at program locality modeling have been made using cluster analysis, neural networks and wavelet theory. As a result, cluster caches based on neural networks have been proposed. This new type of cache offers a hit rate similar to full associative caches with hit times comparable on average to low set associative caches. Traces signatures recognition and compression are derivative experiments made in this area.
CAD Systems for Asynchronous Design Motivation: Asynchronous designs provide potential advantages for VLSI systems of increasing complexity. The Goal: Developing methods and tools for the efficient design of asynchronous systems. Results: (1) Synthesis: A monotonous cover theory is developed. It provides an efficient method for hazard-free technology mapping of speed-independent circuits into simple gates, (2) Verification: Methods for checking the implementability of signal transition graph specifications based on unfoldings and on BDD symbolic traversal are given. (3) Performance: A quasi-linear algorithm for determining the cycle time and the critical cycle of an asynchronous circuit is developed. (4) Testing: A method for stuck-at-i and delay-fault testing of redundant circuits (different design styles) without modifying the logic is proposed. (5) Models and Specification: A generalized event-based model for specifying different types of AND and OR causality is developed.
PMSP Project Overview We are working on PMSP -- Parallel Multithreaded Superscalar Processor project. The goal of the project is to design and implement a multiple-instruction-stream multiple-execution-pipeline processor and to develop an instruction scheduling method for exploiting instruction level parallelism. We have finished the architecture and organization description, developed a performance prediction model, and designed the datapath. Now, we are working on designing the control unit, putting all the circuits together, attempting to reduce the amount of gates required, and developing the instruction scheduling strategy from the compiler's point of view.
Microelectronics/VLSI Course Development Project An on-line tutorial in Japanese for the Cadence software used in the Logic Design exercise class has been developed. A hard copy reference manual (in Japanese) for the Cadence software tool Composer was also written. The tutorial tool was developed based on MOSAIC's multimedia capabilities. The goals of the project were: (1) develop an interactive on-line tutorial which facilitates learning by making use of multimedia and (2) save paper and time. The tutorial may be accessed at /public/www/labs/hw-ca/logictut/Mosaic\_W.
Refereed Journal Papers
The GVIP(geometric and TV image processor)graphics processor, which creates and synthesizes computer graphics and TV image and meets the requirements of multi-media systems, is described. The hardware modules that make up this graphics processor include: a 32-bit embedded RISC processor, a Phong and Gouraud shading processor, a texture mapping processor, a hidden ssurface removal processor, an HDTV video image processor, a BitBlt processor, an image-processing module and an outline font fill generator. These hardware modules fabricated using 0.8 micron CMOS have been placed in three integrated circuit chips. The total number of gates used for on set of chip is approximately 350,000.
Self-timed behavior is verified on the basis of event models. A new model, Change Diagrams (CD), based on two types of causal relations (AND, OR) is introduced. A necessary and sufficient condition for CD implementability by a speed-independent ciruit is considered. A polynomial algorithm for checking CD correctness is given.
The object of this paper is the analysis of asynchronous circuits for speed-independence or delay-insensitivity. The circuits are specified as a netlist of logic functions describing the components. The analysis is based on a derivation of an event specification of the circuit behavior in a form of a Signal Graph. Signal Graphs can be viewed either as a formalization of timing diagrams , or as a signal interpreted version of Marked Graphs (a subclass of Petri Nets). The main advantage of this method is that a state explosion is avoided. A restoration of an event specification of a circuit also helps to solve the behavior identification problem, i.e. to compare the obtained specification with the desired specification. We illustrate the method by means of some examples.
In this paper, we propose to reduce execution time and to gain predictability by making use of a concurrent hardware software scheme for memory hierarchies. Making use of memory hierarchies will allow reducing memory access time while concurrency will relax memory bandwidth resource constraint. The software part of the scheme makes a static analysis of the real time application and generates a file containing special controller instructions. These instructions are generated and scheduled using artificial intelligence optimization techniques so to assure an optimal concurrent management scheme of the memory hierarchy. the hardware part is composed by specially designed memory controllers which are connected to a dedicated bus which allows access to all the memory hierarchy levels. These controllers will execute the instructions associated to the application concurrently with the execution of the application on the microprocessor. Bus contention is avoided between the microprocessor executing the real time application and the controllers on the dedicated bus due to good scheduling generated at compile time.
The increasing power of processors set a challenging problem to the compiler designers. They have to optimize the use of the resources required by a program during its execution to avoid loosing the benefit of this power due to resource conflicts. These resources can either be the registers, the functionnal units or the cache memory which is a small memory that contains the most recently referenced data. These problems are much known as the register allocation problem, the instruction scheduling problem and the cache management problem. In this paper, we propose the use of the A* algorithm for the data cache management problem and propose an admissible heuristic. The algorithm deal with the basic problem butconstitutes the core of a family of algorithms.
The design and control of memory hierarchies greatly affects the performance of microprocessors. Hardware schemes have been proposed to enhance successfully the hit rate of instruction and data caches in various architectures. However, the increasing frequency of microprocessors make hardware schemes unsufficient due to their poor look ahead capability. Compile time schemes make use of the compile time information and of the flow analysis of the program to manage data caches with special hardware support. In this paper, we propose a compile time data cache management algorithm for uniprocessors and proves its optimality. This algorithm is a branch and bound like algorithm making use of heuristics.
In this study, we conducted an empirical static analysis of NASA and CLAPACK benchmarks. Different metrics were measured and their dispersion analyzed. All the programs are written in C and compiled with two different compilers cc and gcc. For each compiler we used both no optimization and full optimization modes. The goal of this study is multiple and attempts to understand more programs structure and programs requirements in order to derive some hints about architectural support or compiler algorithms.
Compile time optimizations have been an intensive research area in uniprocessor environment. However, due to the NP-completeness of most of the problsm dealt with and the various nature of programs, these optimizations have been applied with various successes. While in many cases, it is theoretically possible to solve the problems, in practice the proposed methods run tino space or/and time problems. Based on our experience, we propose the use of a linear space algorithm for the data cache compile time management problem and propose and admissible heuristic. This extends our previous work on the subject and shows the necessity of trade offs and a very fine tuning of the balance between space and time complexity.
In this paper, we shows the use of a linear space best first search algorithm in a cache memory management scheme. The search of an optimal solution is done iteratively and produces a suboptimal solution although with the important advantage of a reduced compile time.
In this paper we propose an approach for compressing address traces with access patterns irregularity. This approach is based on a cluster analysis of the trace. This analysis do not rely on any locality assumption and thus is suitable in case where space locality is poor due to access patterns irregularity. This approach can be used efficiently as a complement to other compression techniques which rely exclusively on locality to achieve their results. As much as 50% reduction in storage requirements have been observed on synthetic traces. On hard traces, the scheme outperform all other existing tchniques amongst them Unix compress. When combined with Unix compress it systematically outperforms all other techniques on the considered traces.
We present in this paper very simple compression experiments using wavelets of computer address traces which are heavily used in Computer Architecture simulation. Trace driven simulation is facing a major obstacle with the sizes of traces used during simulation. These sizes are requiring an increasing amount of storage to be stored and an increasing amount of simulation time to be consumed. We report in this paper some preliminary experiments of using the wavelet theory as a tool to reduce this size. Because of the well established locality nature of computation, a program profile exhibits patterns that we expected to meet the specifications of wavelet theory to be applied with interest. We conducted several experiments on a standard suite of benchmarks used for trace-driven simulations using several filters and thresholding policies. A part from excessive computation time requirements, this approach suffers from unstable behavior with performance varying from poor to excellent.
The GVIP graphics processor is designed to meet the requirements of virtual reality and multi-media systems. It has the first shading processor and synthesizer of computer graphics image with TV image by hardwired logic circuit. This processor can create the image in real-time which is indispensable for virtual reality system of walk-through. It will be used as an application processor for the massive parallel processing system "Aizu Supercomputer system", which is connected with PEs at the bottom layer of a Pyramid Internetwork. One set of processor performs 1 million polygons/sec. and supports 3-dimensional multi-screen with liquid-crystal shutter.
The Aizu supercomputer is a massively parallel system suited to the solution of virtual reality problems and the support of multi-media applications. It employs a highly parallel MIMD architecture using a conflict-free interconnection network system. The scalable communication system consists of two networks: Pyramid and a reconfigurable network using optical links. The Aizu Supercomputer has a cluster configuration and a shared memory. Each PE delivers 113 SPECmark. One cluster is organized with 8 PEs. In the trial production, the supercomputer will include 1365 PEs with more than 100GFlops at peak performance.
Asynchronous circuits behave like concurrent programs implemented in hardware logic. The processes in such circuits are synchronised in accordance with the dynamic logical and causal conditions between switching events. In this paper we investigate a paradigm called OR causality. Petri nets and Change Diagrams provide adequate modelling and circuit synthesis tools for the various OR causality types, yet they do not always bring the specifier to a unique decision about which modelling construct must be used for which type. We present a unified descriptive tool, called Causal Logic Net, which is graphically based on Petri net but has an explicit logic causality annotation for transitions. The signal-transition interpretation of this tool is analogous to, but more powerful than, the well-known Signal Transition Graph. A number of examples demonstrate the usefulness of this model in the synthesis of asynchronous control circuits.
This paper characterizes the speed-independence of high-level designs. The characterization is a condition on the design description ensuring that the behavior of the design is independent of the speeds of its components. The behavior of a circuit is modeled as a transition system, that allows data types, and internal as well as external non-determinism. This makes it possible to verify the speed-independence of a design without providing an explicit realization of the environment. The verification can be done mechanically. A number of experimental designs have been verified.
Existing methods for synthesis of speed-independent circuits under unbounded delay model have difficulties in combining the generality of formal approach with the practicality of the implementation architectures used at the logic level. This paper presents a characteristic property of the state graph specification, called Monotonous Cover requirement, implying its hazard-free implementation within the standard structure of a two-level SOP logic and a row of latches. The overall synthesis procedure ensures satisfiability of this condition by applying the generalised state assignment approach.
Determining the cycle time and critical cycle is a fundamental problem in the analysis of concurrent systems. We solve this problem using timing simulation of an underlying Signal Graph (an extension of Marked Graphs). For a Signal Graph with n vertices and m arcs our algorithm has the polynomial time complexity $O(b^2 *m)$, where b is the nbr of vertices with initially marked in-arcs (typically b << n). The algorithm has a clear semantic and a low descriptive complexity. We illustrate the use of the algorithm by applying it to performance analysis of asynchronous circuits.
A technique for checking safety properties based on high-level specifications with transition system is discussed. A combination of a theorem prover and model checking tools is proposed for effecient hierarchical verification. We demonstrate the method on the example of the speed-independent property.
We review the problems with testing of asynchronous circuits. We show that delay-fault testing is necessary for the good coverage of fabrication defects. A technique for robust path delay testing of asynchronous nets is proposed.
This paper defines conditions for a Signal Transition Graph to be implemented by an asynchronous circuit. A hierarchy of the implementability classes is presented. Our main concern is the implementability of the specification under the restricted input-output interface between the design and the environment, i.e., when no additional interface s ignals are allowed to be added to the design. We develop algorithms and present experimental results of using BDD-traversal for checking STG implementability. These results demonstrate efficiency of the symbolic approach and show a way of improving existing tools for STG-based asynchronous circuit design.
An overview of CAD tools for asynchronous design is given. We attempt to classify tools based on the following parameters: design stage support (verification of specifications, circuit analysis, circuit synthesis, performance analysis, performance/area optimization, library binding, high-level design, testing, design for testability, etc.); model for specification; type of implementation (a delay model, SI/DI/FM/etc., ,a complex/simple gate support, logic library support, transitor level implementation); verification method (in particular, how the problem of a state explosion is attempt to be avoided); synthesis method (modular design, direct compilation, logic synthesis from a state graph, etc.)
Speed-independence is a property of a circuit ensuring correct operating regardless of the magnitude of delays in all its gates. In this paper, circuits are modeled by formal transition systems, and speed-independence is characterized by state predicates expressing constraints on the transition system. This makes it possible to define a formal condition corresponding to speed-independence, and to mechanically verify that a given transition system satisfies the condition. The condition is formulated in such a way that the transition system, and hence also the circuit design, can be checked in a modular way, i.e., by checking the circuit design module by module. This means that large designs can be checked in smaller pieces and without providing an explicit circuit realization of the environment.
An approach for stuck-at-i and delay-fault testing of redundant circuits without modifying the logic is proposed. The only requirement is the ability to control both phases of each variable independent of each other. The circuit becomes fully testable under very weak assumptions, equivalent to freedom from Single Cube Containment in two-level form. The main existing methods for asynchronous circuit synthesis are demonstrated to satisfy the assumptions and then are testable using the methodology. Heuristics to improve the approach include partial scan and non-scan testing.
The idea of analysis is based on the STG unfolding into an acyclic graph. The improved method of unfolding is suggested. Based on this method the verification algorithms of STG analysis are developed. These algorithms are polynomial from the size of STG unfolding. Their efficiency is considered on the set of benchmarks.
In this paper we use the interpreted Petri Nets model for verification of asynchronous circuits. The main property in analysis is the speed-independence of a circuit. The analysis is based on the PN unfolding into an occurrence net. In terms of unfolding the necessary and sufficient conditions for correctness are formulated.
Presentation of the analysis of different models.
Evaluation of synthesis methods.
In the past decade, the performance of single-threaded RISC processors was improved significantly by introducing deep pipeline and by dispatching more than one instruction per cycle. However, such single-threaded RISC processors will no longer significantly increase the processing speed because of the data and control dependencies between the instructions within a single thread. This paper proposes a parallel multithreaded RISC processor architecture and an analytic model which is used to predict its performance and the utilization of multiple functional units. The RISC processor architecture consists of dedicated execution pipelines supporting multiple threads in a uniprocessor environment. The analytic model accepts the configuration parameters of a RISC processor and the instruction distributions of applications. The model provides a quick performance prediction and a quick utilization prediction which are helpful for the processor design. The simulations on numerical and non-numerical programs show that the predictions by the model are quite exact.
Pipelining has been widely used in designing processors for exploiting the parallelism of operations. The potential speed-up of pipelining is equal to the number of pipeline stages used. This advantage encourages engineers to use deeper and deeper pipelines in designing high-performance processors. However, this ideal speed-up is rarely achieved in practice due to lack of sufficient instructions to make multiple pipelines busy and due to delays associated with pipeline dependencies and memory access latencies. Finely Parallel Multithreaded Processor (FPMP) architectures try to solve these problems by dispatching multiple instructions from multiple instruction threads in parallel. This paper proposes an new analytic model which is used to quantify the advantage of FPMP architectures. The effects of four important parameters in FPMP, S, T, E, and F, (STEF) are evaluated, where S is the the number of thread slots that affects the capability of dispatching instructions per cycle, T is the number of instruction threads to be scheduled and it affects the interval cycles of threads interleaving, E is the maximal number of cycles required by execution stage and it affects the interlock delay cycles, F is the number of functional units that affects the structure conflicts. Unlike previous analytic models of multithreaded architecture, the model presented here concerns the performance of multiple pipelines. It deals not only with pipeline dependencies but also with structure conflicts.