To increase memory bandwidth, many programmable Digital Signal Processors (DSPs) employ two on-chip data memories. This architectural feature supports higher memory bandwidth by allowing multiple data memory accesses to occur in parallel. Exploiting dual memory banks, however, is a challenging problem for compilers. This, in part, is due to the instruction-level parallelism, small numbers of registers, and highly specialized register capabilities of most DSPs. In this paper, we present a new methodology based on a genetic algorithm for assigning data to dual-bank memories. Our approach is global, and integrates several important issues in memory assignment within a single model. Special effort is made to identify those data objects that could potentially benefit from an assignment to a specific memory, or perhaps duplication in both memories. Our computational results show that the GA is able to achieve a 54% reduction in the number of memory cycles and a reduction in the range of 7% to 42% in the total number of cycles when tested with well-known DSP kernels and applications.

This paper investigates the problem of routability prediction in a FPGA that employs a hierarchical routing architecture. Such a FPGA is called a hierarchical FPGA (HFPGA). A novel model is proposed to analyze various HFPGA configurations. A software tool has been developed to predict the routability of circuits on specific HFPGA architectures. Primary contribution of this work is that routability prediction can be done immediately after the technology-mapping step, rather than after placement. The effect of connection block and switch block flexibility on routability is also studied. The results show that compared to a symmetrical FPGA architecture we can achieve the same degree of routability on a HFPGA, with much fewer routing switches.

Presents a novel approach to the high-level synthesis problems of scheduling, allocation, and binding for multiblock behavioral descriptions. Our design tool, JOSHUA, uses an integer linear programming (ILP) formulation to solve the three interdependent subproblems simultaneously and optimally. The system allows the designer to minimize time, area, and the number of microwords for the entire design, or for specific segments of the design. A diverse module library provides a selection of modules that can perform a specific operation in differing amounts of time (control steps). A novel feature is the ability to select an implementation for part of an algorithm from among a set of implementation alternatives. The system can also handle the issues of path frequencies, loops, parallel threads of execution, and register allocation.>

The problem of minimizing interconnection complexity in behavioral level synthesis is considered. In particular, it is assumed that logical connection requirements have already been determined, with a corresponding level of multiplexing implied. The total amount of multiplexing is further reduced by combining connections onto shared path segments, when possible. Using the number of equivalent 2*1 multiplexers as the measure of interconnection complexity, the optimum solution to this problem can be guaranteed. The solution technique uses integer linear programming, preceded by a process that reduces the problem space without compromising optimality. It is shown how to minimize the total number of tristate buffers in a bus implementation.>

The authors address the issue of area-time trade off in VLSI circuits using the BILBO methodology of BIST. The issue has been dealt with in an integrated manner. Two distinct approaches, integer linear programming and graph theoretic have been presented.>

When BILBO tests are being generated and scheduled, resource conflicts between I-paths and tests present many difficulties. The authors explore: how pipelining is limited by potential internal conflicts; ways to promote pipelining during test plan generation and how to incorporate a test into a test phase already containing tests that conflict with it. They do not directly address the general problems of test plan generation or test scheduling. What is offered is insight into the difficulties that (potential) conflicts provide and techniques for handling these difficulties. The insights are primarily theoretical, but the resulting techniques could be viewed as possible extensions to existing methodologies.>

The present approaches to automated digital synthesis realise the control using a centralised controller. This paper presents a technique for synthesizing decentralised controllers based on interconnections between control and data path. The algorithm is based on analyzing the control flow and suitably partitioning it to realise decentralised controllers. The controllers, thus synthesized, preserve the control structure in the source description and have simple inter-controller communication. The algorithm is illustrated with an example and the controllers are mapped to pla like structures.

An algorithm to synthesize registers using multiport memories during data-path synthesis is presented. The proposed approach considers not only the access requirements of registers but also their interconnection to operators in order to minimize required interconnections. The same approach can be applied to select the optimum number of buses in a multibus architecture. The method is illustrated with an example.>

This paper proposes a scheme for the representation and processing of fractions in a residue system. The scheme is based on a mixed radix representation of a fraction in a residue, system. The algorithms for basic arithmetic operations of addition, subtraction, and multiplication involving fractions are developed and are shown to provide some improvement over an existing method. Application of these algorithms to division of two integers in the residue system has been shown.

This paper is concerned with the algebraic sign detection of a number in a residue number system. The proposed solution is applicable only to nonredundant systems. The method utilizes a systematic decomposition of the sign function S that is based on some special properties of S. Starting with the canonical sum-of-products expression for S, we transform the expression to a form whose realization is simpler than the canonical form realization and, if possible, also simpler than the minimal sum-of-products realization. In some cases, the proposed method yields savings as high as 85% compared to the minimal sum-of-products realization for S.

This correspondence describes an implementation scheme for the operations of addition and subtraction in the residue number systems. The method is based on the property that the set of residues modulo m form a finite group under addition and subtraction (modulo m). The proposed adder/subtractor structure is very systematic and, hence, suitable for MSI/LSI realization.

Residue arithmetic offers the possibility of "carryfree" arithmetic as far as the operations of addition, subtraction, and multiplication are concerned. It is faster to implement these operations using residue arithmetic as compared to implementation using binary arithmetic. However, the process of algebraic sign detection is much slower in residue arithmetic and tends to offset the advantage of speed in the above three operations.

The problem of minimizing the bit dimension of control memories in microprogrammed digital computers is considered in this paper. We start essentially with the same basic formulation as that of Grasselli and Montanari [2]. However, in order to minimize the computational requirements, we start directly with the set of maximum compatibility classes of microcommands whose number is usually small, and readily obtain near-minimal irredundant solutions. A minimal solution is then obtained from the irredundant solutions.

This paper describes a novel implementation scheme for the operations of addition and subtraction in the residue number systems. The method is based on the property that the set of residues modulo m form a finite group under addition (mod m). Therefore, any row in the modulo m addition table is simply a permutation of the elements of any other row. The effect of this on the implementation scheme is as follows: The set of residues modulo m (o to m-1) are held in a register. For operands X and Y, X is used to permute the contents of the register and Y is used to select the appropriate part of the register to be gated into the sum register.

This paper considers translation problems in residue number systems. The conversion from a fixed-base representation to a residue representation can be done using residue adders only; we show that relatively simple combinational logic can be used to replace one level of residue addition. In the reverse translation problem, we examine the conditions under which base extension can be used to compute the fixed-base digits from a residue code number, and we study the efficiency of the algorithm.

This paper is concerned with the sign detection problem in residue number systems. The proposed solution is applicable only to nonredundant systems. It is shown that under rather general conditions an explicit, closed formula for the sign function can be obtained. In a special case, when one of the moduli is 2, the sign function becomes an EXCLUSIVE-OR function. A sign detection algorithm is proposed and methods of implementing the algorithm are presented.