Narrow Results

In this paper a platform is presented, that given a stochastic context-free grammar (SCFG), automatically outputs the description of the parser in synthesizable hardware description language (HDL) which can be downloaded in an Field Programmable Gate Arrays (FPGA) board. Initially, according to our methodology the SCFG is augmented with attributes which store the probability values and can be evaluated through corresponding stack actions. The architecture of the produced system is based on a proposed extension of Earley’s parallel algorithm, which given an input string, generates the parse trees in the form of an AND-Or parse tree. This AND-or parse tree is then traversed using a proposed tree traversal technique in order to execute the corresponding actions in the correct order, so as to compute the necessary probabilities. The platform is suitable for embedded systems applications where a natural language interface is required or in pattern recognition tasks. The parser generated by the presented platform has been tested for various SCFGs and compared to software approaches. The performance comparison is one to two orders of magnitude in favor of the presented hardware, compared to previous software approaches, depending on the application, the input string length and the number of produced trees.

In this paper, a platform is presented, that given a Stochastic Context-Free Grammar (SCFG), automatically outputs the description of a parser in synthesizable Hardware Description Language (HDL) which can be downloaded in an FPGA (Field Programmable Gate Arrays) board. Although the proposed methodology can be used for various inexact models, the probabilistic model is analyzed in detail and the extension to other inexact schemes is described. Context-Free Grammars (CFG) are augmented with attributes which represent the probability values. Initially, a methodology is proposed based on the fact that the probabilities can be evaluated concurrently with the parsing during the parse table construction by extending the fundamental parsing operation proposed by Chiang & Fu. Using this extended operation, an efficient architecture is presented based on Earley’s parallel algorithm, which given an input string, generates the parse table while evaluating concurrently the probabilities of the generated dotted grammar rules in the table. Based on this architecture, a platform has been implemented that automatically generates the hardware design of the parser given a SCFG. The platform is suitable for embedded systems applications where a natural language interface is required or in pattern recognition tasks. The proposed hardware platform has been tested for various SCFGs and was compared with previously presented hardware parser for SCFGs based on Earley’s parallel algorithm. The hardware generated by the proposed platform is much less complicated than the one of comparison and succeeds a speed-up of one order of magnitude.

We propose an efficient binding algorithm for power optimization in behavioral synthesis. In prior work, it has been shown that several binding problems for low-power can be formulated as multi-commodity flow problems (due to an iterative execution of data flow graph) and be solved optimally. However, since the multi-commodity flow problem is NP-hard, the application is limited to a class of small sized problems. To overcome the limitation, we address the problem of how we can effectively make use of the property of efficient flow computations in a network so that it is extensively applicable to practical designs while producing close-to-optimal results. To this end, we propose a two-step procedure, which (1) determines a feasible binding solution by partially utilizing the computation steps for finding a maximum flow of minimum cost in a network and then (2) refines it iteratively. Experiments with a set of benchmark examples show that the proposed algorithm saves the run time significantly while maintaining close-to-optimal bindings in most practical designs.

A VLSI chip is fabricated by integrating several rectangular circuit blocks on a 2D silicon floor. The circuit blocks are assumed to be placed isothetically and the netlist attached to each block is given. For wire routing, the terminals belonging to the same net are to be electrically interconnected using conducting paths. A staircase channel is an empty polygonal region on the silicon floor bounded by two monotonically increasing (or decreasing) staircase paths from one corner of the floor to its diagonally opposite corner. The staircase paths are defined by the boundaries of the blocks. In this paper, the problem of determining a monotone staircase channel on the floorplan is considered such that the number of distinct nets whose terminals lie on both sides of the channel, is minimized. Two polynomial-time algorithms are presented based on the network flow paradigm. First, the simple two-terminal net model is considered, i.e., each net is assumed to connect exactly two blocks, for which an O(n×k) time algorithm is proposed, where n and k are respectively the number of blocks and nets on the floor. Next, the algorithm is extended to the more realistic case of multi-terminal net problem. The time complexity of the latter algorithm is O((n+k)×T), where T is the total number of terminals attached to all nets in the floorplan. Solutions to these problems are useful in modeling the repeater block placement that arises in interconnect-driven floorplanning for deep-submicron VLSI physical design. It is also an important problem in context to the classical global routing, where channels are used as routing space on silicon.

It has been estimated that multiplexors (MUXes) make up a major portion of the circuitry in a typical chip. Therefore, to reduce power consumption of a chip, it is important to consider the design of MUXes that consumes less power. This is called the low power MUX decomposition problem and has been studied in Ref. 1. This paper improves on the results of Ref. 1 in two ways: (a) we propose a method to speed up the algorithms in Ref. 1, and (b) we propose a post-optimization procedure to further reduce the overall power dissipation of decompositions obtained by any MUX decomposition algorithm. Using this post-optimization procedure, we have been able to further reduce the power dissipation results of Ref. 1.

We propose a new flow for hardware/software co-design, based on the platform-based design, which forms a base for further automation attempts of the co-design process. We prove the applicability of the proposed flow on co-designing generic systems as well as RTOS-based systems. Our proposed flow starts with a software-only solution in which all system functionality is described as embedded software targeting a selected platform. Then, the flow iterates through co-verification, profiling, partitioning, and co-synthesis until the design criteria are met. We present four test cases to show the effectiveness of our proposed methodology. The main contribution added by the proposed methodology is incorporating the target application platform at the first stage of the flow then applying our iterative co-design algorithm without altering the main platform. This opposes other co-design methodologies that let the platform details be synthesized at later stages, widening the exploration space to be unrealistic and producing platforms that may vary to a large extent compared to the pre-verified application platform. The other contribution is the study provided on the effect of co-design on the behavior of RTOS-based platforms, which brings the flow closer to real-case problems, where most embedded systems utilize RTOS in their software stack.

The implementation of regular iterative algorithms (RIAs) in important scientific fields such as image processing, computer arithmetic, cryptography and their implementation in processor arrays architectures, has been extensively studied over the last three decades. Numerous design methodologies and tools have been proposed, mostly targeting custom very large scale integration (VLSI) chips. The advent of field-programmable gate arrays (FPGAs) has attracted many researchers to incorporate previously acquired knowledge and experience in designing VLSI chips, to this new technology. This paper addresses the issue of the implementation of regular algorithms into FPGAs and presents a novel design tool for the implementation of RIAs, formulated as dependence graphs (DGs), on systolic arrays. Furthermore, a platform scheme for the systolic arrays hardware realization is proposed.