In this paper, we describe the software environment for Daytona, a single-chip, bus-based, shared-memory, multiprocessor DSP.The software environment is designed around a layered architecture.Tools at the lower layer are designed to deliver maximum performance and include a compiler, debugger, simulator, and profiler.Tools at the higher layer focus on improving the programmability of the system and include a run-time kernel and parallelizing tools.The run-time kernel includes a low-overhead, preemptive, dynamic scheduler with multiprocessor support that guarantees real-time performance to admitted tasks.1.

The problem of minimizing the cycle time of a given pipelined circuit is considered. The idea of simultaneous retiming and resynthesis is used to optimize a pipelined circuit to meet a given cycle time. An instance of the pipelined cycle optimization problem is specified by the circuit, a set of input arrival times relative to the clock, a set of required output times relative to the clock, and a given cycle time that it must meet. Given the instance of the pipelined performance optimization problem, the authors construct an instance of a combinational speedup problem. This is specified by a combinational logic circuit, a set of arrival times on the inputs, and a set of required times for the outputs which must be met. A constructive proof that the pipelined problem has a solution if and only if the combinational problem has a solution is given. This result shows that it is enough to consider only the combinational speedup problem, and all known techniques for that can be directly applied to generate a solution for the pipelined problem.>

A description is given of SIS, an interactive tool for synthesis and optimization of sequential circuits. Given a state transition table or a logic-level description of a sequential circuit, SIS produces an optimized net-list in the target technology while preserving the sequential input-output behavior. Many different programs and algorithms have been integrated into SIS, allowing the user to choose among a variety of techniques at each stage of the process. It is built on top of MISII and includes all (combinational) optimization techniques therein as well as many enhancements. SIS serves as both a framework within which various algorithms can be tested and compared and as a tool for automatic synthesis and optimization of sequential circuits.>

We present an algorithm to optimally distribute a signal to its required destinations. The choice of the buffers and the topology of the distribution tree depends on the availability of different strength gates and on the load and the required times at the destinations. The general problem is to construct a fanout-tree for a signal so that the required time constraint at the source node is met and the fanout-tree has a minimum area. Since the area constrained fanout problem is NP-complete and area is not a major consideration in present high density designs, we restrict our attention to the simpler problem of designing fast fanout circuits without any area constraint. The proposed algorithm builds the fanout tree by partitioning the fanout signals into subsets and then recursively solving each sub-problem. At each stage the algorithm generates a fanout tree that is an improvement over the previous stage. This feature allows the user to specify the improvement desired by the fanout correction process. The performance of the algorithm, when run on randomly generated distributions of required times and on real design examples, is very promising.

The problem of minimizing the cycle time of a given pipelined circuit is considered. Existing approaches are sub-optimal since they do not consider the possibility of simultaneously resynthesizing the combinational logic and moving the latches using retiming. In the work of S. Malik et al. (Proc. of the Hawaii Inter. Conf. on System Sciences, 1990) the idea of simultaneous retiming and resynthesis was introduced. The authors use the concepts presented in that work to optimize a pipelined circuit to meet a given cycle time. Given an instance of the pipelined performance optimization problem, an instance of a combinational speedup problem is constructed. A constructive proof is given that the pipelined problem has a solution if and only if the combinational problem has a solution. This result is significant since it shows that it is enough to consider only the combinational speedup problem and all known techniques for that domain can be directly applied to generate a solution for the pipelined problem.>

An algorithm for speeding up combinational logic with minimal area increase is presented. A static timing analyzer is used to identify the critical paths. Then a weighted min-cut algorithm is used to determine the subset of nodes to be resynthesized. This subset is selected so that the speedup is achieved with minimal area increase. Resynthesis is done by selectively collapsing the logic along the critical paths and then decomposing the collapsed nodes to minimize the critical delay. This process is iterated until either the timing requirements are satisfied or no further improvement can be made. The algorithm has been implemented and tested on many design examples with promising results.>