State-of-the-art neural network architectures such as ResNet, MobileNet, and DenseNet have achieved outstanding accuracy over low MACs and small model size counterparts. However, these metrics might not be accurate for predicting the inference time. We suggest that memory traffic for accessing intermediate feature maps can be a factor dominating the inference latency, especially in such tasks as real-time object detection and semantic segmentation of high-resolution video. We propose a Harmonic Densely Connected Network to achieve high efficiency in terms of both low MACs and memory traffic. The new network achieves 35%, 36%, 30%, 32%, and 45% inference time reduction compared with FC-DenseNet-103, DenseNet-264, ResNet-50, ResNet-152, and SSD-VGG, respectively. We use tools including Nvidia profiler and ARM Scale-Sim to measure the memory traffic and verify that the inference latency is indeed proportional to the memory traffic consumption and the proposed network consumes low memory traffic. We conclude that one should take memory traffic into consideration when designing neural network architectures for high-resolution applications at the edge.

Power gating is effective for reducing standby leakage power as multi-threshold CMOS (MTCMOS) designs have become popular in the industry. However, a large inrush current and dynamic IR drop may occur when a circuit domain is powered up with MTCMOS switches. This could in turn lead to improper circuit operation. We propose a novel framework for generating a proper power-up sequence of the switches to control the inrush current of a power-gated domain while minimizing the power-up time and reducing the dynamic IR drop of the active domains. We also propose a configurable domino-delay circuit for implementing the sequence. Experimental results based on state-of-the-art industrial designs demonstrate the effectiveness of the proposed framework in limiting the inrush current, minimizing the power-up time, and reducing the dynamic IR drop. Results further confirm the efficiency of the framework in handling large-scale designs with more than 80 K power switches and 100 M transistors.

We propose a simple and effective lossless compression algorithm for video display frames. It combines the dictionary coding, the Huffman coding, and three proposed innovative schemes to achieve a high compression ratio. We quantitatively analyze the characteristics of display frame data for designing the algorithm. We first propose a two-stage classification scheme to classify all pixels into three categories. Then we employ the dictionary coding and propose an adaptive prefix bit truncation scheme to generate codewords for video pixels in each category. We subsequently employ the Huffman coding scheme to assign bit values to the codewords. Finally, we propose a head code compression scheme to further reduce the size of the codeword bits. Experimental results show that the proposed algorithm achieves 22% more reduction than prior arts.

We propose a simple and effective lossless compression algorithm for video display frames. It combines a dictionary-based compression algorithm and the Huffman coding method to achieve a high compression ratio. We quantitatively analyze the characteristics of display frame data and propose the algorithm accordingly. We first use a dictionary-based algorithm and an adaptive quotient bit truncation method to generate codewords for all video pixels. Then, we employ the Huffman coding scheme to assign bit values to the codewords. Finally, we apply a simple algorithm to further reduce the size of the codeword bits. Compared with previous works, the proposed algorithm achieves at least 13% improvement in data reduction ratio.

H.264/AVC intra-frame encoding contains several computation-intensive coding tools that form a long data dependency loop that is difficult to speed up. In this paper, we present a low-power and high-performance H.264/AVC intra-frame encoder. We propose several novel approaches to alleviate the performance bottleneck caused by the long data dependency loop among 4 × 4 luma blocks, integrate an efficient CABAC entropy encoder, and apply a clock-gating technique to reduce power consumption. Synthesized into a TSMC 0.13 μm CMOS cell library, our design requires 265.3 K gates at 114 MHz and consumes 23.56 mW to encode 1080pHD (1920 × 1088) video sequences at 30 frames per second (fps). It also delivers the same video quality as the H.264/AVC reference software. Compared with all state-of-the-art designs, our design has a lower working frequency and achieves both better bit-rate saving and lower power consumption.

In an advanced System-on-Chip (SoC) for real-time applications, the arbiter of its on-chip communication subsystem needs to support multiple QoS criteria while providing a hard real-time guarantee. To fulfill both objectives, the arbitration algorithm must dynamically switch between NonReal-Time (NRT) and Real-Time (RT) modes such that use of the RT mode is minimized to best accommodate the overall QoS criteria. In this article, we define a model for this problem, and propose optimal solutions to its associated problems with static and dynamic warning-zone-length assignment. Compared with previous works, the proposed approach enables a bus arbiter to use much less RT mode in providing a Real-Time (RT) guarantee and, therefore, gives the arbiter more opportunity to employ non-RT modes to achieve better overall QoS. Experimental results show that the proposed approach reduces RT mode usage by as much as 37.1%. Moreover, that reduction in RT mode usage helps cut the execution time by 27.0% when applying our approach to an industrial DRAM controller. Another case study on an AMBA-compliant ultra-high-resolution H.264 decoder IP shows that the proposed approach reduces RT mode usage by 26.4%, which leads to an average reduction of 10.4% in decoding time. Finally, when implementing a 16 master arbiter, it costs only 6.9K and 9.5K gates of overhead using the proposed static and dynamic approach, respectively. Therefore, the proposed approach is suitable for real-time SoC applications.

Variable block size motion estimation (VBSME) is one of several contributors to H.264/AVC's excellent coding efficiency. However, its high computational complexity and huge memory traffic make deign difficult. In this paper, we propose a memory-efficient and highly parallel VLSI architecture for full search VBSME (FSVBSME). Our architecture consists of 16 2-D arrays each consists of 16 × 16 processing elements (PEs). Four arrays form a group to match in parallel four reference blocks against one current block. Four groups perform block matching for four current blocks in a pipelined fashion. Taking advantage of overlapping among multiple reference blocks of a current block and between search windows of adjacent current blocks, we propose a novel data reuse scheme to reduce memory access. Compared with the popular Level C data reuse scheme, our approach can save 98% of on-chip memory access with only 25% of local memory overhead. Synthesized into a TSMC 180-nm CMOS cell library, our design is capable of processing 1920 × 1088 30 fps video when running at 130 MHz. The architecture is scalable for wider search range, multiple reference frames and pixel truncation as well as down sampling. We suggest a criterion called design efficiency for comparing different works. It shows that the proposed design is 72% more efficient than the best design to date.

Variable-block-size motion estimation (VBSME) is one of the contributors to H.264/Advanced Video Coding (AVC)'s excellent coding efficiency. Due to its high computational complexity, however, VBSME needs acceleration for real-time high-resolution applications. We propose a high-performance hardware architecture for H.264/AVC fractional motion estimation. Our architecture consists of three parallel processing engines, one for 4 × 4 and 8 × 8 blocks, one for 8 × 4 and 4 × 8 blocks, and another for the remaining type of blocks. In addition, we propose a resource-sharing scheme which saves 33% of hardware cost for the computation of the sum of absolute transformed difference. Synthesized into a Taiwan Semiconductor Manufacturing Company (TSMC) 180-nm CMOS cell library, our 321-K gate design only needs to run at 154 MHz when encoding a 1920 ×1088 video at 30 frames per second. Compared with a most comparable previous work that consumes 311 K gates and runs at 200 MHz, our proposed architecture is more efficient.

In this paper, a high throughput fully hardwired CABAC encoder is proposed for real-time encoding video of ultra high resolution, e.g., QFHD (3840times2160). We analyze the distribution of bins in various syntax elements and accordingly propose a new architecture which includes an optimized context memory access scheme, a multi-bin binary arithmetic encoder (BAE), and an SE-specific cycle-reduction context modeler for increasing BAE utilization. Our architecture can process up to 8 bins per cycle. Running at 222 MHz, it is capable of real-time encoding QFHD video in the worst case of main profile level 5.1. We have successfully integrated the proposed CABAC encoder into an H.264/AVC encoder system using a multi-media SoC platform.

We propose a high-performance hardwired deblocking filter for H.264/AVC decoding. To decode QFHD (3840 times 2160, i.e., four times full HD) ultra high definition video, we minimize number of processing cycles, working frequency and amount of external memory traffic. We propose a novel filtering order and employ a 5-stage pipelined and resource-shared dual-edge filter to generate two filtering results every cycle. Taking advantage of skip modes, our filter takes only 48 cycles to filter a macroblock in the best case and 100 in the worst case. Furthermore, it eliminates most unnecessary off-chip memory traffic with a novel on-chip memory scheme. Our design can support QFHD at 30 fps application by running only at 98 MHz.

In an ultra high resolution H.264/AVC decoder, accessing reference frame data stored in DRAM requires huge bandwidth. The access patterns of Motion Compensation (MC) and De-blocking Filter (DF) are very different. Therefore, straightforward access and arbitration may amplify access penalty and, thus, diminish DRAM efficiency. We propose three schemes, access pattern uniformization, Macro Block (MB)-column-based mapping and task-based arbitration, to minimize the DRAM access latency including both penalty and amount of transferred data. Experimental results on a pure hardwired QFHD (3840×2160) H.264/AVC decoder system shows that by employing the proposed schemes, we achieve 86% saving in DRAM access latency.

Variable-block-size motion estimation (VBSME) is a major contributor to H.264/AVC’s excellent coding efficiency. However, its high computational complexity and memory requirement make deign difficult. In this paper, we propose a memory-efficient hardware architecture for full-search VBSME (FSVBSME). Our architecture consists of sixteen 2-D arrays each consists of 16×16 processing elements (PEs). Four arrays form a group to match in parallel four reference blocks against one current block. Four groups perform block matching for four current blocks in a consecutive and overlapped fashion. Taking advantage of reference pixel overlapping between multiple reference blocks of a current block and between search windows of several adjacent current blocks, we propose a novel data reuse scheme to reduce memory access. Compared with the popular Level C data reuse method, our design can save 98% of on-chip memory access with only 27% of memory overhead. Synthesized into a TSMC 130nm CMOS cell library, our design takes 453K logic gates and 2.94K bytes of on-chip memory. Running at 130MHz, it is capable of processing 1920×1088 30fps video with 64×64 search range (SR) and two reference frames (RF). We suggest a criterion called design efficiency for comparing different related work. It shows that our design is 27% more efficient than the best design to date.

We present a high-performance hardware architecture for H.264/AVC full-mode intra-frame encoding. We propose a novel method to alleviate performance bottleneck caused by the long data dependency loop among 4x4 blocks. Synthesized into a TSMC 0.13..m CMOS cell library, our design takes 212K gates to run at 138MHz and is able to real-time encode 1080HD (1920x1088) video sequences at 30 frames per second (fps). Compared with all state-of-the-art designs, our design needs lower working frequency, supports high resolution up to 1080HD and achieves better bit-rate saving.

Multiple-reference-frame, quarter-pixel accuracy, and variable-block-size motion estimation (VBSME) employed in H.264/AVC is one of the major contributors to its outstanding compression efficiency and video quality. However, due to its high computational complexity, VBSME needs acceleration for real-time application. We propose a high throughput hardware architecture for H.264/AVC fractional motion estimation (FME). The proposed architecture consists of three parallel processing engines. In addition, we propose a resource sharing method which leads to 50% hardware saving in the computation sum of absolute transformed difference (SATD). Synthesized into a TSMC 130 nm CMOS cell library, our design takes 311.7K gates at 154 MHz and can encode 1080 pHD video at 30 frames per second (fps). Compared to previous works, the proposed design runs at much lower frequency for the same resolution and frame rate.

Motion Compensation (MC) is the computation bottleneck in H.264/AVC decoding and it dominates DRAM traffic. To alleviate computation loading, we employ two interpolation engines and fully utilize them in both P and B slices. Compared with a traditional separate 1-D interpolation engine, our proposed approach can reduce 79% of average computation latency. To reduce memory traffic, we propose a High Efficiency Reference Frame Pre-Fetch Scheme (HERPS) that saves 91% of multiple reference frame memory access cycles by rearranging access patterns. The overall design costs 117K gates when running at 200MHz and supports up to the QFHD (3840×2160) at 30 frames per second (fps) using a 128-bit DRAM memory system.

We present a high-performance hardwired context-based adaptive binary arithmetic decoder (CABAD) for H.264/AVC. Based on an analysis of decoding time for different types of syntax elements, we propose three parallel processing techniques. Our decoder takes 309 clock cycles to decode a typical I-type macroblock. It needs to run at only 45 MHz for 1080HD application. Therefore, our architecture is suitable for low power mobile applications.

We give a tutorial on video coding principles and standards with emphasis on the latest technology called H.264 or MPEG-4 part 10. We describe a basic method called block-based hybrid coding employed by most video coding standards. We use graphical illustration to show the functionality. This paper is suitable for those who are interested in implementing video codec in embedded software, pure hardwired, or a combination of both.

We propose a near optimal hardware architecture for deblocking filter in H.264/MPEG-4 AVC. We propose a novel filtering order and a data reuse strategy that result in significant saving in filtering time, local memory usage, and memory traffic. Every 16-16 macroblock requires 192 filtering operations. After a few initialization cycles, our 5-stage pipelined architecture is able to perform one filtering operation per cycle. Compared with some state-of-the-art designs, our architecture delivers the fastest level of performance while using much smaller gate count and memory. We have implemented and integrated the proposed deblocking filter into an H.264 main profile video decoder and verified it with an FPGA prototype.

We propose a high performance architecture for fractional motion estimation and Lagrange mode decision in H.264/AVC. Instead of time-consuming fractional-pixel interpolation and secondary search, our fractional motion estimator employees a mathematical model to estimate SADs at quarter-pixel position. Both computation time and memory access requirements are greatly reduced without significant quality degradation. We propose a novel cost function for mode decision that leads to much better performance than traditional low complexity method. Synthesized into a TSMC 0.13 mum CMOS technology, our design takes 56 k gates at 100 MHz and is sufficient to process QUXGA (3200times2400) video sequences at 30 frames per second (fps). Compared with a state-of-the-art design operating under the same frequency, ours is 30% smaller and has 18 times more throughput at the expense of only 0.05 db in PSNR difference

We present our experience of designing a single-chip controller for an advanced digital still camera from specification all the way to mass production. The process involves collaboration with camera system designer, IP vendors, EDA vendors, silicon wafer foundry, package and testing houses, and camera maker. We also co-work with academic research groups to develop a JPEG codec IP and memory BIST and SOC testing methodology. We cover the problems encountered, our solutions, and lessons learned.

We propose an efficient test scheduling and test access architecture for system-on-chip. The test time and test control complexity are optimized under the test power and test access mechanism (TAM) resource constraints. Using our heuristic algorithms, the test scheduling can be done rapidly with small test time penalty when compared with previous works. Under an existing SoC test framework, the test access hardware can be generated from the scheduling result. Experimental results show that the proposed scheduling is hardware efficient. The system integrator can evaluate the test access architecture and perform rest scheduling systematically.

The test scheduling of memory cores can significantly affect the test time and power of system chips. We propose a test scheduling algorithm for BISTed memory cores to minimize the overall testing time under the test power constraint. The proposed algorithm combines several approaches for a near-optimal result, based on the properties of BISTed memory cores. By proper partitioning, an analytic exhaustive search finds optimal results for large memory cores, while a heuristic ordering with simulated annealing further handles a large amount of smaller memory cores. On the average, the results are within 1% difference of the optimal solution for the cases of 200 memory cores.

We propose a performance-driven cell placement method based on a modified force-directed approach. A pseudolink is added to connect the source and sink flip-flops of every critical path to enforce their closeness. Given user-specified input-output pad locations at the chip boundaries and starting with all core cells in the chip center, we iteratively move one cell at a time to its force-equilibrium location assuming all other cells are fixed. The process stops when no cell can be move farther than a threshold distance. Next, cell rows are formed one at a time starting from the top and bottom. After forming these two cell rows (top/bottom), all remaining movable core cells' force-equilibrium locations are updated. The row-formation-and-update process continues until all rows are formed and, hence, a legal placement is obtained. We have integrated the proposed approach into an industrial automatic placement-and-route flow. Experimental results on benchmark circuits up to 191-K cell (500-K gate) show that the critical path delay can be improved by as much as 17%. Our layout quality is independent of initial placement. We also study the effect on both layout quality and central processing unit time consumption due to the amount of pseudolinks added. We found that the introduction of pseudolink indeed significantly improves the layout quality. We also empirically demonstrated that the proposed approach is effective in reducing the total half-perimeter wirelength metric.

We propose a 3-step approach for whole-chip detail routing. In the first step, we construct a performance-driven Steiner tree for each net ignoring the existence of other nets. In the second step, we optimally assign significant wire segments of all trees to the tracks of a two-dimensional, two-layer grid under the design rule constraint. Finally, in the third step, we complete the remaining local short connection between net terminals and those assigned wire segments and resolve any violations or congestion. We have incorporated this approach into an industrial VDSM design flow. Experimental results on large benchmark circuits implemented in a TSMC 0.18um CMOS process have demonstrated the effectiveness of the proposed approach. We achieve more than 14% improvement over a state-of-art commercial performance-driven router in a critical path delay. Our tool can be viewed as a preprocessor for a router. Users do not have to change their existing design flow. Only a small time-efficient step is needed to achieve the performance gain.

We propose a performance-driven cell placement method based on a modified force-directed approach. A pseudo net is added to link the source and sink flip-flops of every critical path to enforce their closeness. Given user-specified I/O pad locations at the chip boundaries and starting with all core cells in the chip center, we iteratively move a cell to its force-balanced location assuming all other cells are fixed. The process stops when no cell can be moved farther than a threshold distance. Next, cell rows are adjusted one at a time starting from the top and bottom. After forming these two rows (top/bottom), all movable core cells force-balanced locations are updated. The row-formation-and-update process continues until all rows are adjusted and, hence, a legal placement is obtained.

Article Free Access Share on Array allocation taking into account SDRAM characteristics Authors: Hong-Kai Chang Department of Computer Science, National Tsing Hua University, Hsinchu, 300, Taiwan, R.O.C. Department of Computer Science, National Tsing Hua University, Hsinchu, 300, Taiwan, R.O.C.View Profile , Youn-Long Lin Department of Computer Science, National Tsing Hua University, Hsinchu, 300, Taiwan, R.O.C. Department of Computer Science, National Tsing Hua University, Hsinchu, 300, Taiwan, R.O.C.View Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 497–502https://doi.org/10.1145/368434.368769Online:28 January 2000Publication History 9citation238DownloadsMetricsTotal Citations9Total Downloads238Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

No abstract available.

We propose an exact clustering with retiming algorithm to minimize the clock period for sequential circuits.Without moving ip-ops (FF's) by retiming, conventional clustering algorithms can only handle combinational parts and therefore cannot achieve the best cycle time.Pan et al. [2] have proposed an optimal algorithm under the unit gate delay m o d e l .W e propose a more powerful and faster algorithm that produces optimal results even under the more realistic general gate delay model.Experimental results show that our algorithm is twice as fast as Pan's.

As feature sizes shrink to deep sub-micron, the performance of VLSI chips becomes dominated by the interconnect delay. In a traditional top-down design flow, logic synthesis algorithms optimize gate area or delay without accurate interconnect delay because of lack of physical design information. Thus, the effectiveness of the optimization techniques is limited. We integrate logic synthesis and physical design into an iterative procedure for performance optimization. The logic synthesis process can optimize circuit delay based on accurate interconnect delay information extracted from the physical design. The physical design tools can refine the layout incrementally with the engineering change information and changed netlist passed from the logic synthesis process. In this thesis, we integrate logic decomposition, gate sizing and buffer insertion to work together to improve the circuit speed. Experimental results on a set of benchmark circuits show that the techniques are indeed effective.

In this paper, we present a complete chip design method which incorporates a soft-macro resynthesis method in interaction with chip oorplanning for area and timing improvements.We develop a timing-driven design ow to exploit the interaction between HDL synthesis and physical design tasks.During each design iteration, we resynthesize soft macros with either a relaxed or a tightened timing constraint which is guided by the post-layout timing information.The goal is to produce area-ecient designs while satisfying the timing constraints.Experiments on a number of industrial designs have demonstrated that by eectively relaxing the timing constraint of the non-critical modules and tightening the timing constraint of the critical modules, a design can achieve 13% to 30% timing improvements with little to no increase in chip area.

In this paper, we present a complete chip design method which incorporates a soft-macro placement and resynthesis method in interaction with chip floorplanning for area and timing improvements. We present a performance-driven soft-macro clustering and placement method which preserves hardware descriptive language (HDL) design hierarchy to guide the soft-macro placement process. We develop a timing-driven design flow to exploit the interaction between HDL synthesis and physical design tasks. During each design iteration, we resynthesize soft macros with either a relaxed or a tightened timing constraint which is guided by the post-layout timing information. The goal is to produce area-efficient designs while satisfying the timing constraints. Experiments on a number of industrial designs ranging from 75-K to 230-K gates demonstrate that the proposed soft-macro clustering and placement method improves critical-path delays on an average of 22%. Furthermore, the results show that by effectively relaxing the timing constraint of noncritical modules and tightening the timing constraint of critical modules, a design can achieve 11% to 30% timing improvements with little to no increase in chip area.

We propose a microcode-optimizing method targeting a programmable DSP processor. Efficient generation of microcodes is essential to better utilize the computation power of a DSP processor. Since most state-of-the-art DSP processors feature some sort of irregular architectures and most DSP applications have nested loop constructs, their code generation is a nontrivial task. In this paper, we consider two features frequently found in contemporary DSP processors — structural pipelining and heterogeneous registers. We propose a code generator that performs instruction scheduling and register allocation simultaneously. The proposed approach has been implemented and evaluated using a set of benchmark core algorithms. Simulation of the generated codes targeted towards the TI TMS320C40 DSP processor shows that our system is indeed more effective compared with a commercial optimizing DSP compiler.

We propose a new layer assignment approach for the klayer Constrained Via Minimization (CVM) problem.We transform the problem into a constrained k-way graph partitioning one.Practicfl issues such as pin-out constraint, over-the-cd constraint, and overlapping between wire segments of the same net, have d been taken into consideration.We propose a motied simdated-anneahng program for the problem.A set of large routing restits generated by a commercial three-layer router has been used to test the effectiveness of the program.Up to 70% reduction of vias has been observed.Assuming an additional fourth layer is avdable, more reduction is achieved.This work is the first to demonstrate the feasibfity of via minimization for practical-sized mtiti-layer layout.It is &o app~cable to future design with more layers.

Retiming relocates registers in a circuit to shorten the clock cycle time. In deep sub-micron era, conventional pre-layout retiming cannot work properly because of dominant interconnection delay that is not available before layout. Although some retiming algorithms incorporating interconnection delay have been proposed, layout information is still not utilized effectively nor efficiently. Retiming and layout is combined for the first time in this paper. We present heuristics for two key problems: interconnection delay estimation and post-retiming incremental placement. An efficient retiming algorithm incorporating interconnection delay is also proposed. Experimental results show that on the average we can improve the circuit speed by 5:4% targeted toward a 0:5um CMOS technology. Scaling down the technology to 0:1um, as much as 25:6% improvement have been achieved. 1 Introduction Retiming is a sequential logic optimization technique proposed by Leiserson and Saxe [1]. It relocates reg...

In this paper, we present a performance-driven soft-macro clustering and placement method which preserves HDL design hierarchy to guide the soft-macro placement process. We also present a complete chip design methodology by integrating the proposed method and a set of commercial EDA tools. Experiments on three industrial designs ranging from 75K to 230K gates demonstrate that the proposed soft-macro clustering and placement method improves critical-path delay on an average of 24%.

With Internet access available to virtually every one in this community it is interesting to investigate on how Internet will affect the future of VLSI design and CAD. We will describe an experimental WWW-based computing broker. Theoretically, the broker is capable of providing every user with access to any hardware platforms and any software over the Internet. It makes possible pay-per-use of both hardware and software resources. It also automatically manages multiple resources ranging from a few seats within an organization to thousands of seats anywhere with the Internet access. This new model of resource usage will have significant impact on the users, the software developers, and the computer vendors. Users no longer have to own nor maintain expensive computers and software tools before they can start their projects. They will have more flexibility in allocating resources to meet the project schedule. Also they will be able to access to the latest technology at lower overall cost. Tool developers and computer vendors will have broader customer base with very little marketing and field support effort. This new model will also provide a better chance for new tools and new platforms.

Article Preserving HDL synthesis hierarchy for cell placement Share on Authors: Yu-Wen Tsay Department of Computer Science, Tsing Hua University, Hsinchu, Taiwan, 300, Republic of China Department of Computer Science, Tsing Hua University, Hsinchu, Taiwan, 300, Republic of ChinaView Profile , Wen-Jong Fang Department of Computer Science, Tsing Hua University, Hsinchu, Taiwan, 300, Republic of China Department of Computer Science, Tsing Hua University, Hsinchu, Taiwan, 300, Republic of ChinaView Profile , Allen C.-H. Wu Department of Computer Science, Tsing Hua University, Hsinchu, Taiwan, 300, Republic of China Department of Computer Science, Tsing Hua University, Hsinchu, Taiwan, 300, Republic of ChinaView Profile , Youn-Long Lin Department of Computer Science, Tsing Hua University, Hsinchu, Taiwan, 300, Republic of China Department of Computer Science, Tsing Hua University, Hsinchu, Taiwan, 300, Republic of ChinaView Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997 Pages 169–174https://doi.org/10.1145/267665.267709Online:01 April 1997Publication History 6citation193DownloadsMetricsTotal Citations6Total Downloads193Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In a hardware emulator consisting of multiple field-programmable gate arrays (FPGAs), the utilization of the FPGA logic resource is usually very low due to the limitation on the number of I/O pins. Virtual wire technology not only increases the inter-FPGA communication capability, but it also increases the logic resource utilization by means of time division multiplexing (TDM). TDM allows one physical wire to be shared by multiple logical wires. For TDM to be effective, each transportation of an inter-FPGA signal must be carefully assigned to a slot of the time division. In this note, we show that the phase assignment problem is exactly same as the resource-constrained operation scheduling problem. We adopt the static-list scheduling heuristic for the task, and present some experimental results on a set of benchmark circuits from the MCNC. The experiments show that the proposed method can increase the number of effective I/O pins as many as ten times.

We survey recent developments in high level synthesis technology for VLSI design. The need for higher-level design automation tools are discussed first. We then describe some basic techniques for various subtasks of high-level synthesis. Techniques that have been proposed in the past few years (since 1994) for various subtasks of high-level synthesis are surveyed. We also survey some new synthesis objectives including testability, power efficiency, and reliability.

Traditionally, it is assumed that every variable in the input HDL (hardware description language) behavioral description needs to be held in a register; a register can be shared by multiple variables if they have mutually disjointed lifetime intervals. This approach has been shown effective for signal-flow-like computations such as various DSP algorithms. However, the same is not true for the synthesis of control-dominated circuits, which usually have variables of different bit-width as well as very long lifetime. To go beyond register minimization by lifetime-analysis-based sharing, we propose holding some variables in the state registers, some signal nets, some unclocked sequential networks or a combination of above. We identify the conditions in which the substitution is feasible. We have implemented the proposed method in a software program called VReg. Experimental results have demonstrated that VReg minimizes the number of registers more effectively than the lifetime-analysis-based approach does. Better register area minimization also generally leads to faster designs.

High-level synthesis (HLS) has been successfully targeted towards the digital signal processing (DSP) domain.Both application-speci c integrated circuits (A-SICs) and application-speci c instruction-set processor (ASIPs) have been frequently designed using the HLS approach.Since most ASIP and DSP processors provide multiple addressing modes, and, in addition to classical constraint on the number of function units, registers, and buses, there a r e many resource usage rules, special considerations need t o b e p aid to the optimizing code generation problem.In this paper we propose three t r ansformation techniques, data management, data ordering, and transformational retiming, for storage optimization during code generation.With these transformations, some scheduling bottlenecks are eliminated, redundant instructions removed, and multiple operations mapped onto a single one.The proposed t r ansformations have been implemented in a software system called Theda:MS.A set of benchmark programs has been used to evaluate the eectiveness of Theda:MS.M e asurement on the synthesized c o des targeted towards the TI-TMS320C40 DSP processor shows that the proposed approach is indeed very eective.

Traditionally, it is assumed that every variable in the input HDL (Hardware Description Language) behavioral description needs to be held in a register; A register can be shared by m ultiple variables if they have m utually disjoint lifetime intervals.This approach is eective for signal-ow-like computations such a s v arious DSP algorithms.However, it is not the best for the synthesis of control-dominated circuits, which usually have v ariables/signals of dierent bit-width as well as very long lifetime.To g o b ey ond register minimization by lifetime-analysis-based sharing, we propose holding some variables in the state registers, some signal nets, or some unclocked sequential networks.We h a v e implemented the proposed method in a software program called VReg.Experimental results have demonstrated that VReg minimizes the number of registers more eectively than the lifetime-analysis-based approach does.Better register minimization also leads to both smaller area and faster designs.

We describe a routing method for the design of a class of RAM-based field programmable gate arrays (FPGA). We model the interconnect resources as a graph. A routing solution is represented as a set of disjoint trees, each connecting all terminals of a net, on the graph. An expansion router is used for connecting a net. Initially, nets are connected independently of one another. Conflicts among nets over the usage of interconnect resources are resolved iteratively by a rip-up and rerouter, which is guided by a simulated evolution-based optimization technique. The proposed approach has been implemented in a program called TRACER-fpga. As compared with CGE and SEGA, TRACER-fpga in general requires fewer routing tracks at the expense of longer wiring delay. It is suitable for low-speed applications such as hardware emulation.>

We combine technology mapping and placement into a single procedure, M.Map, for the design of RAM-based FPGAs. Iteratively, M.Map maps several subnetworks of a Boolean network into a number of CLBs on the layout plane simultaneously. For every output node of the unmapped portion of the Boolean network, many ways of mapping are possible. The choice of which mapping to be used depends not only on the location of the CLB into which the output node will be mapped but also on its interconnection with those already mapped CLBs. To deal with such a complicated interaction among multiple output nodes of a Boolean network, multiple ways of mappings and multiple number of CLBs, any greedy algorithm will be insufficient. Therefore, we use a bipartite weighted matching algorithm in finding a solution that takes the global information into consideration. With the availability of the partial placement information, M.Map is able to minimize the routing delay in addition to the number of CLBs. Experimental results on a set of benchmarks demonstrate that M.Map is indeed effective and efficient.>

We propose a cell placement method for row-based integrated circuit layout. The proposed method cleverly utilizes the structural properties of the circuits. It first extracts strongly connected subcircuits, called cones, from the circuit and then groups small cones, called fragments, to reduce the number of cones. The algorithm then performs a macro-cell placement, treating each cone as a soft macro. Next, it maps the resulting macro-cell placement into a row-based placement. Finally, it applies a simulated-annealing procedure to refine the row-based placement. It is able to produce, in a shorter period of CPU time, a higher quality placement compared to classical simulated-annealing-based placement methods as demonstrated by some experimental results on the MCNC benchmarks.>

We address the problem of state assignment to minimize both area and power dissipation for finite state machine designs. We propose a new matching-based state-assignment algorithm which considers area and state transitions simultaneously. Experimental results on a set of benchmarks demonstrate that our approach is indeed very effective in minimizing both area and power dissipation.>

This paper addresses the interconnection synthesis problem in microarchitecture-level designs. With emphasis on the speed of data movement operations, we propose algorithms that take into consideration the effect of each data-transfer-to-bus binding on the data transfer delay time. The delay time is calculated as a function of both data source load and data carrier (bus) load. By balancing loads among hardware components, the data transfer delay time (hence the total execution time) is shortened. We consider two types of problems: resource-constrained binding and performance-constrained binding. Two integer linear programming (ILP) formulations are derived to optimally solve the problems. In order to speed up the computation, a bipartite weighted matching method for the resource-constrained binding and a greedy merging method for the performance-constrained binding are also proposed. Both the ILP formulation generators and the heuristics have been programmed. Experimental results indicate that the proposed algorithms are indeed very effective in optimizing the performance aspect of the interconnection design.>

We propose a transformation-based scheduling algorithm for the problem given a loop construct, a target initiation interval and a set of resource constraints, schedule the loop in a pipelined fashion such that the iteration time of executing an iteration of the loop is minimized. The iteration time is an important quality measure of a data path design because it affects both storage and control costs. Our algorithm first performs an As Soon As Possible Pipelined (ASAPp) scheduling regardless the resource constraint. It then resolves resource constraint violations by rescheduling some operations. The software system implementing the proposed algorithm, called Theda.Fold, can deal with behavioral loop descriptions that contain chained, multicycle and/or structural pipelined operations as well as those having data dependencies across iteration boundaries. Experiment on a number of benchmarks is reported.>

We combine technology mapping and placement into a single procedure, M.map, for the design of RAM-based FPGAs. Iteratively, M.map maps several subnetworks of the Boolean network into a number of CLBs on the layout plane simultaneously. For every output node of the un-mapped portion of the Boolean network, many ways of mapping are possible. The choice depends on the location of the CLB into which the output node will be mapped as well as the interconnection with those already mapped CLBs. To deal with such a complicated interaction among multiple output nodes, multiple ways of mappings and multiple CLBs, any greedy algorithms will be insufficient. Instead, we use a bipartite weighted matching algorithm to find a globally optimum solution. With the availability of the partial placement information. M.map is able to minimize the routing delay in addition to the number of CLBs. Experimental results on a set of benchmarks demonstrate that M.map is indeed very effective in minimizing the real delay (after routing) as well as the number of CLBs.

The authors point out that pipelining is an effective method for optimizing the execution of a loop, especially for digital signal processing (DSP) applications where data enter a circuit regularly. Although throughput and turnaround time are two important optimization criteria, previous work emphasized mainly the throughput. It is shown that the delay time for executing an iteration of a loop has a strong relationship to the cost of the registers and the controller. By minimizing the delay, there is more silicon area to allocate to additional resources, which in turn increases throughput. Forward scheduling and a backward scheduling are iteratively used to achieve this purpose. The algorithm, called PipeLining Scheduler or PLS, can be used to pipeline a loop with or without loop-carried dependencies. Real examples are used to illustrate the method. Experiments on benchmark examples show that considerable improvement over previous approaches is attained.>

A layout style that enables either an automatic layout synthesizer or a layout designer to take full advantage of the second metal layer available from today's technology is proposed. The style not only facilitates power/ground diffusion overlapping but also simplifies the intracell routing problem by having power/ground in the middle and routing in the upper and the lower constraint-free regions. An automatic leaf cell layout synthesizer, called THEDA.P, that is based on the proposed style has been implement. Using the same transistor placement algorithm, THEDA.P outperforms a synthesizer based on T. Uehara and W.M. van Cleemput's (1981) approach by almost 20% in layout compactness across a wide range of small-scale integrated circuits. THEDA.P has been used to build a standard cell library that was previously handcrafted. Results from designing two modules show that THEDA.P's layout quality is very competitive.>

The problem of scheduling a loop in a pipelined fashion such that the iteration time (turnaround time) is minimized, given a loop behavior, a target initiation interval, and resource constraints, is considered. The iteration time is an important quality measure of a data path design because of its direct correlation with both the storage and the control costs. The scheduler starts with performing as-soon-as-possible-pipelined (ASAP/sub p/) scheduling without regard to the resource constraint. It then resolves the resource constraint violations, if there are any, by repeatedly rescheduling some operations.>

The authors present a systolic algorithm and its variations for the k-nearest neighbors problem (kNNP). Multiple-shot queries with different ranges (k values) can be served in a pipelined fashion. A partitioning scheme is developed to handle large size problems. Performance of the algorithm is analyzed. Formulas for the optimal array size in terms of computation time and area-time-time product (ATT) are derived. The algorithm can solve a multiple-shot kNNP in N+2 square root N*K systolic steps using square root N*K processing elements, where N is the problem size (i.e. the number of points), and K is the sum of all k-values.>

We present an algorithm for pipelining loop execution in the presence of loop catried dependence.We optimize both the initiation interval and the turn around time of a schedule.Given constraints on the number of functional units and buses, we tirst determine an initiation interval and then incrementally partition the operations into blocks to fit into the execution windows.A refinement procedure is inwrporated to improve the turn around time.The novel feature which differs our approach from others is that the scheduled operations me iteratively moved up and down to accommodate the ready yet unscheduled opera-tio~.The algorithm produces very encourageous results.

We propose a new layout style that enables an automatic layout synthesizer to take full advantage of the second metal layer available from today's technology.our style not only facilitates power/grotmd-diffttsion overlapping but also sirnplities the intra-cell routing problem.We have implemented an automatic layout synthesizer, called THEDA.P (Tsing Hua Electronic Design Automation), based on the proposed style.Using the same transistor placement algorithm, THEDA.P outperforms a synthesizer based on [Ueh8 1]'s style by almost 20% in layout mmpacmess across a wide range of SS1 circuits.THEDA.P has been used to build a standard cell library that was previously handcrafted.Results from designing two ASIC modules show that THEDA.P's layout quality is very competitive.

We propose a new approach for reducing the density of a channel by routing some nets (or subnets) over the cells (i.e.outside the channel).Previous research assumed that the more nets being routed over the cells the greater the reduction in the channel density.We show that only the removal of critical nets contributes to the reduction in the channel density.We divide channel into zones where each zone has a zone density and the removal of any net from a zone will reduce its density by one.In order to reduce the channel density, only certain critical zones need to have their nets routed over the cells.A bipwtite graph is used to represent the relationship between nets and zones.The problem is transformed into a constrained covering problem and formulated as an integer liiear programming problem.In comparison with previous research our approach reduces more channel densities while using fewer tracks over the cells.For Deutsch's difficult channel, previous approach needs 15 &acks over the cells to reduce the channel density by 3 while we need only 5 tracks to achieve the same result.

The authors present an approach that combines logic minimization and folding for a programmable logic array (PLA). An efficient algorithm is proposed for optimal bipartite column folding. In the algorithm, the authors model the PLA personality matrix as a network and the bipartite PLA folding as a partitioning problem of that network. This folding algorithm is able to find optimal solutions for the benchmarks from the literature. The algorithm also substitutes product terms by their alternatives in order to find the one best suited for folding. The authors combine this algorithm and a logic minimization algorithm into a folding system. When comparing the results to those by a conventional approach, about one half of the benchmarks show area gain if product-term-alternatives exist.>

An automatic layout generation system, called LiB, for the small-scale integrated (SSI) cells used in CMOS VLSI design, is presented. LiB takes a transistor-level circuit schematic in SPICE format and outputs a mask layout in CIF. The layout style is a modification of that proposed by T. Uehara, and W. M. van Cleemput (IEEE Trans. Comput., vol.C-30, no.5, p.305-12, 1981). An optimal transistor chaining algorithm has been developed to derive a transistor placement with a minimum number of diffusion separations. To meet the cell height constraint, large transistors are folded into multiple columns algorithmically. The whole cell is divided into five routing regions. Two are on the diffusion island and the others are rectilinear-shaped routing channels. A graph-theoretic method for selecting nets (subnets) for routing on the diffusion island is proposed. A global routing algorithm has been developed to assign the remaining nets to the three rectilinear channels. For the detailed routing SILK, a simulated evolution router, is employed. LiB can be used as a cell library builder or as a subsystem of a random logic module generator. Users can alternate LiB's layout using a symbolic editor.>

An approach for reducing the density of a channel by routing some nets (or subnets) over the cells (i.e., outside the channel) is proposed. It is shown that only the removal of critical nets contributes to the reduction in the channel density. The channel is divided into zones, each having a zone density where the removal of any net from a zone will reduce its density by one. To reduce the channel density, only certain critical zones need to have their nets routed over the cells. A bipartite graph is used to represent the relationship between nets and zones. The problem is transformed into a constrained covering problem and formulated as an integer linear programming problem. Compared to previous research, the approach reduces more channel densities while using fewer tracks over the cells. For Deutsch's difficult channel, a previous approach needs 15 tracks over the cells to reduce the channel density by 3, whereas the present needs only 5 tracks to achieve the same result. >

We present an automatic layout generation system, called LiB, for the library cells used in CMOS ASIC design. LiB takes a transistor-level circuit schematic in SPICE format and outputs a symbolic layout. Our layout style is similar to that proposed by Uehara and van Cleemput in [17]. We propose several heuristic algorithms to solve the transistor-clustering, -pairing, -chaining, -folding, the chain placement, the routing, and the net assignment problems, respectively. Experimental results are presented to show the capability of LiB.

We propose a graph-theoretic approach for the data path allocation problem. We decompose the problem into three subproblems: (1) register allocation, (2) operation assignment, and (3) connection allocation. The first two subproblems are modeled as two bipartite weighted matching problems and solved using the Hungarian Method [Pap82]. The third subproblem is solved using a greedy method. While previous researches suffer controversy over which one of subproblems (1) and (2) should be done first, we show that, by taking the other into consideration while performing one, equally satisfactory results can be obtained. We have implemented two programs, LYRA and ARYL, to solve the subproblems in different orders, namely, “(1), (2), then (3)” and “(2), (1), then (3)”, respectively. The matching paradigm allows us to take a more global approach toward the problem than previous researches do. For register allocation, our approach is the first one to guarantee minimal usage of registers while being able to take the interconnection cost into account. For all the benchmarks from the literature, both LYRA and ARYL produced designs as good as, if not better than, those by others in very short time. This research has demonstrated that the bipartite weighted matching algorithm is indeed a very good solution for the data path allocation problem.

This paper presents an integer linear programming model for the scheduling problem in high level synthesis under resource constraints. Extensive consideration is given to the following applications:

A fast algorithm is proposed for the transistor-chaining problem in CMOS functional cell layout based on the layout style of T. Uehara and W.M. van Cleemput (1981). The algorithm takes a transistor-level circuit schematic and outputs a minimum set of transistor chains. Possible diffusion abutments between the transistor pairs are modeled as a bipartite graph. A depth-first search algorithm is used to search for the optimal chaining. Theorems on the set of branches that needs to be explored at each node of the search tree are derived. A theoretical lower bound on the size of the chain set is also derived. This bound enables one to prune the search tree efficiently. The algorithm has been implemented and tested and is able to find optimal solutions almost instantly for all the cases from the literature that were examined.>

A general-purpose routing algorithm for very-large-scale integrated (VLSI) circuits and printed circuit board (PCB) designs is proposed. Ideas behind the maze-running algorithm and the hierarchical routing algorithm are combined into a powerful algorithm called hybrid routing. The new algorithm demonstrates a speed compatible to a hierarchical router and produces routings with quality equivalent to that obtained by a maze router. Hybrid routing is based on the maze-running method with a third search dimension added. The extra search space is built by recursively constructing a hierarchy of coarser grid meshes. By means of a parameter-controlled expansion into the coarser meshes, the hybrid router is able to find the preferred search region very quickly and will not miss local information as a hierarchical router does. A user-given parameter can turn the algorithm into a pure maze router, a pure hierarchical router, or a wide spectrum of hybrid routers with different speed/quality characteristics between the extremes. The algorithm has been implemented and integrated into a global router that can handle large-scale routing, such as that encountered in the sea-of-gates layout.>

A fast algorithm is produced for the optimal transistor chaining problem in CMOS functional cell layout based on T. Uehara and W.M. van Cleemput's layout style (IEEE Trans. Comput., vol. C-30, p.305-12, May 1981). The algorithm takes a transistor-level circuit schematic and outputs a minimum set of chains. Possible diffusion abutments between the transistor pairs are modeled as a bipartite graph. A depth-first search algorithm is used to search for the optimal chaining. Theorems on the number of branches needed to be explored at each node of the search tree are derived. A theoretical lower bound on the size of the chain set is derived. This bound enables pruning the search tree efficiently. The algorithm has been implemented and tested. It is able to find optimal solutions almost instantly for all the cases available to use from the literature.>

A novel approach is presented to the operation scheduling problem in a data path synthesis. After obtaining the start time and the require time of each operation by the ASAP (as soon as possible) and ALAP (as late as possible) methods, respectively, an integer linear programming (ILP) formulation is formed to solve the scheduling problem. The objective is to fully utilize the hardware resources, i.e. to minimize the requirement of function units under a given timing constraint. The formulation can be generalized to support multicycle operations, multiple operations per cycle, pipelined data paths, mutually exclusive operations, and variables' lifetime consideration in a data path. A fifth-order filter containing 26 addition and 8 multiplication operations can be scheduled optimally for the cases from 17 cycles to 21 cycles per minute on a VAX-11/8800.>

A general-purpose routing algorithm is proposed. Ideas behind both the maze-running algorithm and the hierarchical routing algorithm are combined into a hybrid routing algorithm. The new algorithm demonstrates a speed compatible to a hierarchical router and produces routings with quality equivalent to that by a maze router. Hybrid routing is based on the maze-running method with a third search dimension added. The extra search space is built by recursively constructing a hierarchy of coarser grid meshes. A user-given parameter can turn this algorithm into a pure maze router, a pure hierarchical router, or a wide spectrum of hybrid routers with different speed/quality characteristics between the extremes. With this approach, it is possible to handle easily a routing of large size, such as those encountered in the sea-of-gate layout.>

The authors present a rip-up-and-rerouter based on a matrix representation scheme and simulated evolution technique for solving detailed routing problems in VLSI layout. The status of the routing region is represented as a matrix. Rip-up and reroute operations are emulated as matrix subtractions and additions, respectively. The quality of a routing result can be measured by a few simple matrix operations on the matrix. A rip-up and reroute switch-box/channel router, called SILK, using a simulated evolution technique has been implemented based on this representation alone. Experimental results showed that SILK, when solving all the benchmarks from the literature, outperformed WEAVER, the most successful switch-box router to date, in both quality and speed aspects.>

A representation scheme for a rip-up and rerouter is presented. The status of the routing region is represented as a four-dimensional matrix. Rip-up and re-route operations are emulated as matrix subtractions and additions, respectively. The quality of a routing result can be measured by performing a few simple matrix operations. A rip-up and reroute switch-box/channel router called SILK, using a simulated evolution technique, has been implemented on the basis of this representation scheme. Experimental results showed that SILK outperformed WEAVER, the most successful switch-box router to date, in both quality and speed aspects, for all the classical benchmarks available.>

The LES expert system for layout generation of random logic modules in a hierarchical CMOS VLSI design system is described. It applies a combination of rule- and algorithmic-based techniques on a novel layout style. The layout style utilizes silicon area more efficiently than a previously developed style. Experimental results have demonstrated the superiority of this expert system against various standard-cell systems and its competitiveness with human designers.>

In this paper we describe an expert system for layout generation in a hierarchical VLSI design system. It applies a combination of rule- and algorithmic-based techniques on a new layout style. Experimental results have demonstrated the superiority of this expert system against various standard-cell systems and its competitiveness with human designers.