Modern embedded CPU systems rely on a growing number of software features, but this growth increases the memory footprint and increases the need for efficient instruction and data caches. The embedded operating system will often juggle a changing set tasks in a round-robin fashion, which inevitably results in cache misses due to conflicts between different tasks. Our technique reduces cache misses by continuously monitoring CPU cache misses to grade the performance of running tasks. Through a series of step-wise refinements, our software system tunes the round-robin ordering to find a better temporal sequence for the tasks. This tuning is done dynamically during program execution and hence can adapt to changes in work load or external input stimulus. The benefits of this technique are illustrated using an ARM processor running application benchmarks with different cache organizations and round-robin scheduling techniques.

The latency of broadcast/reduction operations has a significant impact on the performance of SIMD processors. This is especially true for associative programs, which make extensive use of global search operations. Previously, we developed a prototype associative SIMD processor that uses hardware multithreading to overcome the broadcast/reduction latency. In this paper we show, through simulations of the processor running an associative program, that hardware multithreading is able to improve performance by increasing system utilization, even for processors with hundreds or thousands of processing elements. However, the choice of thread scheduling policy used by the hardware is critical in determining the actual utilization achieved. We consider three thread scheduling policies and show that a thread scheduler that avoids issuing threads that will stall due to pipeline dependencies or thread synchronization operations is able to maintain system utilization independent of the number of threads.

The performance of SIMD processors is often limited by the time it takes to transfer data between the centralized control unit and the parallel processor array. This is especially true of hybrid SIMD models, such as associative computing, that make extensive use of global search operations. Pipelining instruction broadcast can help, but is not enough to solve the problem, especially for massively parallel processors with thousands of processing elements. In this paper, we describe a SIMD processor architecture that combines a fully pipelined broadcast/reduction network with hardware multithreading to reduce performance degradation as the number of processors is scaled up.

Soft CPU cores are often used in embedded systems, yet they limit opportunities to improve cache performance to hardware assistance outside the CPU core. Instruction prefetching is commonly used, but the popular Prefetch On Miss (POM) technique is less helpful when the instruction flow does not follow a sequential execution order, which is often the case in real-time networking applications. Cluster Miss Prediction (CMP) can help in those worst case situations when cache misses do not follow a sequential order, and can be combined with POM to provide an effective technique for real-time networking applications on embedded systems. The benefits of the CMP+POM technique are illustrated in the context of an industrial embedded networking application using different cache configurations.

In this paper, we describe a new method of instruction prefetching that reduces the cache miss penalty by anticipating the cache behavior based on previous execution. Our observations indicate that instruction cache misses often repeat in clusters under certain conditions prevalent in real time embedded networking systems. By identifying the start of a cluster miss sequence and preparing an instruction buffer for the upcoming cache misses, the miss penalty can be reduced if a miss does occur. A sample industrial networking example is used to illustrate the effectiveness of this technique compared with other prefetch methods.

Summary form only given. This paper describes the implementation and use of a dedicated associative SIMD coprocessor ideally suited for many applications such as database processing, image processing, genome matching, or molecular similarity analysis. The concept of associative SIMD processing is introduced, and differentiated from other associative and SIMD techniques. Then our ASC (associative computing) processor is briefly described, along with its implementation of associative SIMD processing. Finally, we demonstrate the use of our ASC processor on relational database processing and on the image processing operation of edge detection.

This paper describes an initial design of an associative processor for implementation using field-programmable logic devices (FPLDs). The processor is based loosely on earlier work on the STARAN computer, but updated to reflect modern design practices. We also draw on a large body of research at Kent State on the ASC and MASC models of associative processing, and take advantage of an existing compiler for the ASC model. The resulting design consists of an associative array of 8-bit RISC Processing Elements (PEs), operating in byte-serial fashion under the control of an Instruction Stream (IS) Control Unit that can execute assembly language code produced by a machine-specific back-end compiler.

One of the primary advantages of a high-level synthesis system is its ability to explore the design space. This paper presents several methodologies for design space exploration that compute all optimal tradeoff points for the combined problem of scheduling, clock-length determination, and module selection. We discuss how each methodology takes advantage of the structure within the design space itself as well as the structure of, and interactions among, each of the three subproblems. (CAD)

One of the primary advantages of a high-level synthesis system is its ability to explore the design space. This paper presents several methodologies for design space exploration that compute all optimal tradeoff points for the combined problem of scheduling, clock length determination, and module selection. We discuss how each methodology takes advantage of both the structure within the design space itself as well as the structure of, and interaction between, each of the three subproblems.

This paper describes several new algorithms for computing lower bounds on the length of the schedule and the number of functional units in high-level synthesis.

This paper describes the development and content of a "VLSI Design" course. We had two main goals for the course: to develop a one-semester course for computer science (and other) majors, and to give the students practical experience with real industrial tools. To meet those goals, we provided only enough material on logic design and IC operation to orient the students, focused on FPLD-based design, and used high-quality design tools. We also found a wealth of free material available on the web, including course information, entire textbooks, and extensive technical data.

This paper describes an exact solution methodology, implemented in Rensselaer's Voyager design space exploration system, for solving the scheduling problem in a three-dimensional (3-D) design space: the usual two-dimensional (2-D) design space (which trades off area and schedule length), plus a third dimension representing clock length. Unlike design space exploration methodologies which rely on bounds or estimates, this methodology is guaranteed to find the globally optimal solution to a 3-D scheduling problem. Furthermore, this methodology efficiently prunes the search space, eliminating provably inferior design points through the following: 1) a careful selection of candidate clock lengths and 2) tight bounds on the number of functional units or on the schedule length. Both chaining and multicycle operations are supported.

The authors present a new polynomial-time algorithm for computing lower bounds on the number of functional units (FUs) of each type required to schedule a data flow graph in a specified number of control steps. A formal approach is presented that is guaranteed to find the tightest possible bounds that can be found by relaxing either the precedence constraints or integrality constraints on the scheduling problem. This tight, yet fairly efficient, bounding method can be used to estimate FU area, to generate resource constraints for reducing the search space, or in conjunction with exact techniques for efficient optimal design space exploration.

In integer linear programming (ILP), formulating a "good" model is of crucial importance to solving that model. In this paper, we begin with a mathematical analysis of the structure of the assignment, timing, and resource constraints in high-level synthesis, and then evaluate the structure of the scheduling polytope described by these constraints. We then show how the structure of the constraints can be exploited to develop a well-structured ILP formulation, which can serve as a solid theoretical foundation for future improvement. As a start in that direction, we also present two methods to further tighten the formulation. The contribution of this paper is twofold: 1) it provides the first in-depth formal analysis of the structure of the constraints, and it shows how to exploit that structure in a well-designed ILP formulation, and 2) it shows how to further improve a well-structured formulation by adding new valid inequalities.>

We present a new algorithm for cluster-oriented scheduling (COS) in pipelined data path synthesis. First, cluster structure information is extracted from the corresponding linear graph representation of a data flow graph (DFG). Then, scheduling and allocation globally interact with the cluster information under the timing constraints of pipeline latency and data initialization interval (DII). Using this technique, the costs of registers, multiplexors, and interconnection were reduced dramatically in both the FIR and elliptic filter examples.>

Presents a general treatment of the combinatorial approach to the scheduling problem, enhancing previous formulations in the literature. The focus of this paper is a formal analysis of the integer linear programming (ILP) approach, which we use to evaluate the structure of our formulation. Polyhedral theory and duality theory are used to demonstrate that efficient solutions of the scheduling problem can be expected from a carefully formulated integer linear program. Furthermore, we use the theory of valid inequalities to tighten the constraints and make the formulation more efficient.>

Most high-level synthesis systems act as "black boxes", with the user allowed minimal interaction during the synthesis process.To allow the user to take a more active role, using his or her creativity where appropriate, advances must be made in three key areas.Better metrics must be developed, to allow the user to quickly evaluate the quality of the design at various points in the synthesis process, and to identify developing problem areas in the design.Better interaction techniques must be devised to allow the user to observe, control, and interact with the synthesis tools.Finally, as a foundation for these metrics and synthesis tools, a well-designed graphical user interface must be developed, this interface must be able to display both small and large designs, and must support mechanisms to control the display complexity.These are three important issues to address in making high-level synthesis a practical design tool.

An attempt was made to define the algorithmic level of design (also known as the behavioral level) and to provide the designer with the means to explore various design issues. Within the framework of the System Architect's Workbench, a new set of behavioral and structural transformations was developed to allow the interactive exploration of algorithmic-level design alternatives. A description is given of these transformations, and a set of examples is presented both to demonstrate the application of the transformations and to further illustrate their effects.>

To represent the increasingly complex designs being produced today, we have developed1 a unified model of design representation that uses three hierarchical, non-isomorphic domains of description that can be coordinated to represent the entire design. Each of these domains contains multiple levels of abstraction; both the domains and the levels are described in detail in this paper. We then show how this model of design representation can be used as a model of design synthesis. It is hoped that this work will lead to a better understanding of design representation and its relationship to the synthesis process.