10053237
Automated least-significant bit datapath optimization for FPGAs
In this paper, we present a method for FPGA datapath precision optimization subject to user-defined area and error constraints. This work builds upon our previous research which presented a methodology for optimizing the dynamic range- the most significant bit position. In this work, we present an automated optimization technique for the least-significant bit position of circuit datapaths. We present results describing the effectiveness of our methods on typical signal and image processing kernels.
15600737
Least-significant bit optimization techniques for FPGAs
We present a methodology for FPGA datapath precision optimization subject to user-defined area and error constraints. This work builds upon our previous research which presented a methodology for optimizing for dynamic range--the most significant bit position. In this work we define the problem of least significant bit optimization and propose optimization techniques that provide finer control of area-to-error tradeoffs than more traditional methods. We present some preliminary results describing the effectiveness of our techniques on typical signal and image processing kernels.
14617128
Harvest Rate of Reconfigurable Pipelines
For a reconfigurable architecture, the harvest rate is the expected percentage of defect-free processors that can be connected into the desired topology. The authors give an analytical estimation for the harvest rate of reconfigurable multipipelines based on the following model: there are n pipelines each with m stages, where each stage of a pipeline is defective with identical independent probability 0.5 and spare wires are provided for reconfiguration. By formulating the "shifting" reconfiguration as weighted chains in a partial ordered set, they prove when n=/spl theta/(m), the harvest rate is between 34% and 72%.
11770804
Measuring dynamic memory invocations in object-oriented programs
Dynamic memory management has been a high cost component in many software systems. Studies have shown that memory intensive C programs can consume up to 30% of the program runtime in memory allocation and liberation. The OOP language system tends to perform object creation and deletion prolifically. An empirical study shown that C++ programs can have ten times more memory allocation and deallocation than comparable C programs. However, the allocation behavior of C++ programs is rarely reported. This paper attempts to locate where the dynamic memory allocations are coming from and report an empirical study of dynamic memory invocations in C++ programs. Firstly, this paper summarizes the hypothesis of situations that invoke the dynamic memory management explicitly and implicitly. They are: constructors, copy constructors, overloading assignment operator=, type conversions and application specific member functions. Secondly, the development of a source code level tracing tool is reported as the procedure to investigate the hypothesis. Thirdly, results include behavioral patterns of memory allocations. With these patterns, we may increase the reusability of the resources. For example, a profile-based strategy can be used to improve the performance of dynamic memory management. The C++ programs that were traced include Java compiler, CORBA compliant and visual framework.
16824799
A heuristic method for self‐healing ring design in a single‐homing cluster
In this paper, we consider a SONET (Synchronous Optical NETwork) USHR (Uni‐directional Self‐Healing Ring) design problem for a single‐homing cluster, i.e., a cluster with a single designated hub. The problem is formulated as a nonlinear integer programming problem and a branch and bound heuristic method based on the Lagrangian relaxation and subgradient optimization technique is proposed to handle the problem. In solving any ring design problem, we should deal with two different aspects of the ring design, namely, the ring routing aspect and the ring loading aspect. Both of these two aspects are well integrated and represented in our model. Such an integrated formulation has not been proposed in the existing literature mainly due to its computationally intractable complexity. In order to cope with such complexity, a preprocessing technique for reducing the complexity and several branch and bound strategies are proposed. The efficiency of the proposed method is tested through computational experiments. For the computational experiments, test problems are generated using the data obtained from the actual topologies in Seoul, Korea. The computational experiments show that the proposed method yields near‐optimum designs within reasonable computation time.
6580714
Optimal Diagnosis Procedures for k-out-of-n Structures
Diagnosis strategies are investigated for repairable VLSI and WSI structures based on integrated diagnosis and repair. Knowledge of the repair strategy, the probability of each unit being good, and the expected test time of each unit is used by the diagnosis algorithm to select units for testing. The general problem is described, followed by an examination of a specific case. For k-out-of-n structures, a complete proof is given for the optimal diagnosis procedure of Y. Ben-Dov (1981). A compact representation of the optimal diagnosis procedure is described, which requires O(n/sup 2/) space and can be generated in O(n/sup 2/) time. Simulation results are provided to show the improvement in diagnosis time over online repair and offline repair. >
207137932
On-Line Chinese Character Recognition by Incorporating Human Knowledge
A stroke order and number free method for on-line recognition of Chinese characters is proposed. Both input characters and the model characters are represented with complete attributed relational graphs (ARGs). The ARGs of the model base are built according to the human knowledge of the segment relation structure of Chinese characters. For the recognition purpose, an optimal matching measure between two ARGs is defined, and the graph matching is formulated as a search problem of finding the minimum cost path in a state space tree, using the A* algorithm. Moreover, to reduce the search time of the A*, besides a heuristic estimate, a novel strategy is employed which again uses the human knowledge of the segment position structure of Chinese characters to prune the tree. Our experimental results demonstrate the efficiency of the proposed method.