Performance estimation is an essential technique in computer system design and optimization. Traditional time-quantum-based methods have limitations in accurately capturing program behavior due to the granularity issue. In this paper, we propose a novel approach, called Basic-Block-based Frequency Domain Analysis (BBFDA), that uses basic block analysis to extract program execution phase information and applies recursive frequency domain analysis to estimate performance waveforms. We evaluate our proposed approach on SPEC CPU2017 benchmark suites and compare it with time-quantum-based methods. Results show that our approach achieves higher accuracy and robustness than traditional methods, especially for cases with many phases. Our proposed approach can dynamically track performance behavior without the need to choose an appropriate granularity size.

An effective full-system virtual prototype is critical for early-stage systems design exploration. Generally, however, traditional acceleration approaches of virtual prototypes cannot accurately analyze system performance and model non-deterministic inter-component interactions due to the unpredictability of simulation progress. In this paper, we propose an effective virtualization-assisted approach for modeling and performance analysis. First, we develop a deterministic synchronization process that manages the interactions affecting the data dependency in chronological order to model inter-component interactions consistently. Second, we create accurate timing and bus contention models based on runtime operation statistics for analyzing system performance. We implement the proposed virtualization-assisted approach on an off-the-shelf System-on-Chip (SoC) board to demonstrate the effectiveness of our idea. The experimental results show that the proposed approach runs 12~77 times faster than a commercial virtual prototyping tool and performance estimation is only 3~6% apart from real systems.

In this paper we extend the concept of the traditional transactor, which focuses on correct content transfer, to a new timing-coherent transactor that also accurately aligns the timing of each transaction boundary so that designers can perform precise concurrent system behavior analysis in mixed-abstraction-level system simulations which are essential to increasingly complex system designs. To streamline the process, we also developed an automatic approach for timing-coherent transactor generation. Our approach is actually applied in mixed-level simulations and the results show that it achieves 100% timing accuracy while the conventional approach produces results of 25% to 44% error rate.

We propose a new embedded processor power analysis approach that maps instruction executions to microarchitecture components for highly efficient and accurate power evaluations, which are crucial for embedded system designs. We observe that in practice, the execution of each high-level instruction in a processor always triggers the same microcomponent activity sequence while the difference of power consumption values of different instructions is mainly due to timing variations caused by hazards and cache misses. Hence, by incorporating accurately pre-characterized microcomponent power consumption values into an efficient instruction-microcomponent processor timing simulation tool, we construct a highly accurate embedded processor power analysis tool. Additionally, based on the proposed approach, we accurately and effortlessly capture the power waveform at any time point for power profiling, peak power and dynamic thermal distribution analysis. The experimental results show that the proposed approach is nearly as accurate as gate-level simulators, with an error rate of less than 1.2% while achieving simulation speeds of up to 20 MIPS, five orders faster than a commercial gate-level simulator.

Multicore instruction-set simulation (MCISS) has become more and more important due to tremendous increase in number of multicore designs. To boost the speed of MCISS, one of the most effective and commonly used approaches is parallel simulation. However, timing synchronization must be applied to ensure accurate simulation results of parallel MCISS, and may induce huge synchronization overhead. In this paper, we propose a highly efficient and effective parallel MCISS approach by synchronizing timing before each synchronization function (SF) call. We improve the applicability of the state-of-the-art critical-section-level simulation approach with a generic blocking/nonblocking send/receive model covering all types of SFs. To further reduce synchronization overhead, we also introduce optimization methods such as a hybrid scheduling technique and provide an analysis algorithm that helps the designers to choose the host platform with the best simulation performance. Experiments show that the proposed approach attains a simulation speed of up to 285 MIPS, while producing accurate timing and functional results.

As modern systems are integrating exceeding number of components for better performance and functionality, early full-system simulation tools have become essential for validating complex concurrent system interaction activities. In the past decades, many useful timing-accurate system simulation tools have been developed; however, we find that even for the most efficient techniques, more than 90% of overhead occurs when simulating shared devices, such as buses. Instead of adopting the constant-delay model that compromises accuracy or using the time-consuming precise scheduling approach, we propose in this paper an effective system activity-sensitive contention delay model that can dynamically capture runtime contention situations and system configuration changes. To verify the idea, we construct an analytical bus delay model and integrate that into a system simulation tool. The experimental results show 20 to 80 times performance improvement over the scheduling-based bus model on full-system simulations and the estimated timing difference is less than 3%.

Due to process limitations, wiring rules are imposed by foundries on chip layout. Under nanometer wiring rules, the required separation between two wire ends is dependent on their surrounding wires, and there is a limit on the minimum length of each wire segment. Yet, traditional maze routing algorithms are not designed to handle these rules, so rule violations are corrected by post-processing and the quality of result is seriously impacted. For this reason, we propose a new maze routing algorithm capable of handling these wiring rules. The proposed algorithm is proved to find a legal shortest path with time complexity of O(n), where n is the number of grid points. Experiments with seven tight industrial cases show that the runtime of a commercial router is reduced by 2.4 times and the total wire length is also reduced by 3% on average.

Multi-core system simulation techniques have been especially essential to system development in recent years. Although these techniques have been studied extensively, we have found that both conventional polling and collaborative timing synchronization approaches all encounter a severe scalability issue when the number of target cores is more than that of the host cores. To resolve this issue, we propose an effective hybrid technique that combines the advantage of the two approaches. According to the experimental results, the proposed technique effectively resolves the scalability issue and shows one to four orders of improvement compared to conventional approaches.

This paper proposes a Critical-Section-Level timing synchronization approach for deterministic Multi-Core Instruction-Set Simulation (MCISS). By synchronizing at each lock access instead of every shared-variable access and using a simple lock usage status managing scheme, our approach significantly improves simulation performance while executing all critical sections in a deterministic order. Experiments show that our approach performs 295% faster than the shared-variable synchronization approach on average and can effectively facilitate system-level software/hardware co-simulation.

We propose a new power simulation technique that effectively considers dynamic program execution behaviors such as cache hit/miss or branch predicted/mis-predicted and achieves fast and accurate power estimation results. Traditionally, accurate software power estimation relies on slower fine-grained simulations while faster coarse-grained simulations often lead to inaccurate estimation results. We pre-characterize detailed circuit power consumption, pipeline and branch effects of each basic block for accuracy and then apply efficient instruction-set simulators to compute total software power consumption. The experimental result shows that our approach achieves over 200 MIPS performance with a less than 3% error rate.

Due to process limitations, wiring rules are imposed on chip layout by foundries. Under nanometer wiring rules, the required separation between two wire ends is dependent on their surrounding wires, and there is a limit on the minimum length of each wire segment. However, traditional shortest path algorithms are not properly designed for these rules. In the paper, we propose a maze routing algorithm, called MANA, capable of finding legal shortest paths under these rules. Experiments with seven industrial cases show that by handling these rules during maze routing, 94% of the violations are prevented on average, and the overall runtime of a commercial router is reduced by 71%. In addition, the total wire length is also reduced by 3% on average.

Although pipelined/out-of-order (PL/OO) execution features are commonly supported by the state-of-the-art bus designs, no existing manual Transaction-Level-Modeling (TLM) approaches can effectively construct fast and accurate simulation models for PL/OO buses. Mainly, the inherent high design complexity of concurrent PL/OO behaviors makes the manual approaches tedious and error-prone. To tackle the complicated modeling task, this article presents an automatic approach that performs systematic abstraction and generation of fast-and-accurate simulation models. The experimental results show that our approach reduces 21 times modeling efforts, while our generated models perform simulation an order of magnitude faster than Cycle-Accurate models with the same PL/OO transaction execution cycle counts preserved.

As multi-core architecture has become the mainstream, the corresponding multi-core instruction-set simulation (MCISS) is also needed to aid system development. Ideally, we may run a MCISS in parallel to enhance the simulation speed. However, the conventional centralized timing synchronization mechanism would greatly constrain the parallelism of a MCISS, so the simulation speed is bounded. To resolve this issue, we propose a new distributed timing synchronization technique which allows higher parallelism for a MCISS. Hence, it accelerates the simulation speed by 9 to 20 times as the number of cores increases in contrast to the centralized synchronization approach.

This paper proposes using a non-intrusive timing synchronization interface approach to facilitate shared-data synchronization for fast and accurate hardware-assisted HW/SW co-simulation. Our synchronization interface device is specially designed for non-transparent components. With the device, we can systematically monitor shared-data accesses on a bus and control the progressing time of hardware-assisted components for fast and accurate system co-simulation. Experiments show that our approach is 10 to 140 times faster than the cycle-based hardware-assisted co-simulation approach.

In this article, we propose an extended SystemC framework that directly enables software simulation in SystemC. Although SystemC has been widely adopted for system-level simulation of hardware designs nowadays, to complete HW/SW co-simulation, it still requires an additional instruction set simulator (ISS) for software execution. However, the heavy intercommunication overheads between the two heterogeneous simulators would significantly slow down simulation performance. To deal with this issue, our proposed approach automatically generates high-speed and equivalent SystemC models for target software applications that can be directly integrated with hardware models for complete HW/SW co-simulation. In addition, to properly handle multitasking, an efficient OS model is devised to support accurate preemptive scheduling. Since both the generated application model and the OS model are constructed in SystemC modules, our approach avoids heavy intercommunication overheads and achieves over 1,000 times faster simulation than that of the conventional ISS-SystemC approach. Experimental results demonstrate that our extended SystemC approach can perform at 50 to 220 MIPS while offering accurate simulation results.

To successfully route a design, one essential requirement is to allocate sufficient routing resources. In this paper, we show that allocating routing resources based on horizontal and vertical (H/V) cut-demands can greatly improve routability especially for designs with thin areas. We then derive methods to predict the maximum H/V cut-demands and propose two cut-demand based approaches, one is to allocate routing resources considering the maximum H/V cut-demands and the other is to consolidate fragmented metal-1 routing resources for effective resource utilization. Experimental results demonstrate that the resource allocation method can precisely determine design areas and the resource consolidation method can significantly improve routability. With better routability, the routing time is about 5 times faster on average and the design area can be further reduced by 2-15%.

Ideally, multi-core instruction-set simulation should run in parallel to improve simulation performance. However, the conventional low-parallelism centralized scheduler greatly constrains simulation performance. To resolve this issue, we propose a high-parallelism distributed scheduling mechanism. The experimental results show that our proposed approach accelerates simulation by 6 to 20 times, depending on the number of cores.

This paper proposes a shared-variable-based approach for fast and accurate multi-core cache coherence simulation. While the intuitive, conventional approach - synchronizing at either every cycle or memory access - gives accurate simulation results, it has poor performance due to huge simulation overloads. We observe that timing synchronization is only needed before shared variable accesses in order to maintain accuracy while improving the efficiency in the proposed shared-variable-based approach. The experimental results show that our approach performs 6 to 8 times faster than the memory-access-based approach and 18 to 44 times faster than the cycle-based approach while maintaining accuracy.

Ideally, system-level simulation should provide a high simulation speed with sufficient timing details for both functional verification and performance evaluation. However, existing cycle-accurate (CA) and cycle-approximate (CX) processor models either incur low simulation speeds due to excessive timing details or low accuracy due to simplified timing models. To achieve high simulation speeds while maintaining timing accuracy of the system simulation, we propose a first cycle-count-accurate (CCA) processor modeling approach which pre-abstracts internal pipeline and cache into models with accurate cycle count information and guarantees accurate timing and functional behaviors on processor interface. The experimental results show that the CCA model performs 50 times faster than the corresponding CA model while providing the same execution cycle count information as the target RTL model.

Operating system (OS) models are widely used to alleviate the overwhelmed complexity of running system-level simulation of software applications on specific OS implementation. Nevertheless, current OS modeling approaches are unable to maintain both simulation speed and accuracy when dealing with preemptive scheduling. This paper proposes a Data-dependency-Oriented Modeling (DOM) approach. By guaranteeing the order of shared variable accesses, accurate simulation results are obtained. Meanwhile, the simulation effort of our approach is considerably less than that of the conventional Cycle-Accurate (CA) modeling approach, thereby leading to high simulation speed, 42 to 223 million instructions per second (MIPS) or 114 times faster, than CA modeling as supported by our experimental results.

In this paper, the author discusses how ideas from academic research are adapted into making physical design tools that are both successful and practical. Excluding recent developments, the author uses his past experiences to review the thinking process of selecting appropriate algorithms and the progressive optimization idea for creating effective design tools. The review mainly focuses on routability and timing optimization issues, though the ideas presented in the paper can be applied or extended to new tool development.

This paper proposes a source-level timing annotation method for generation of accurate transaction level models for software computation modules. While transaction level modeling (TLM) approach is widely adopted now for system modeling and simulation speed improvement, timing estimation accuracy often is compromised. To have reliable and accurate estimation results at system level, we propose a timing annotation method for accurate TLM computation model generation considering processor architecture with pipeline and cache structures, which are challenging but critical to accurate timing estimation. The experiments show that our results are within 2% of cycle accurate results and the approach is three orders faster than conventional ISS approaches.

This paper proposes a novel software Transaction-Level Modeling (TLM) approach for efficient HW/SW co-simulation. In HW/SW co-simulation, timing synchronization should be involved between the hardware and software simulations for keeping their concurrency. However, improperly handling timing synchronization either slows down the simulation speed or scarifies the simulation accuracy. Our approach performs timing synchronization only at the points of HW/SW interactions, so the accurate simulation result can be achieved efficiently. Furthermore, we define three abstraction levels of software TLM models based on the type of interactions captured. Given the target software, the software TLM models can be automatically generated in multiple abstraction layers. The experimental results show that our software TLM models attain 3 million instructions per second (MIPS) for low-level abstraction and go as high as 248 MIPS for higher level abstraction. Therefore, designers can have efficient co-simulation by selecting a proper layer according to the abstraction of corresponding hardware components.

This paper proposes the first automatic approach to simultaneously generate cycle accurate and cycle count accurate transaction level bus models. Since TLM (transaction level modeling) is proven as an effective design methodology for managing the ever-increasing complexity of system level designs, researchers often exploit various abstraction levels to gain either simulation speed or accuracy. Consequently, designers repeatedly perform the time-consuming task of re-writing and performing consistency checks for different abstraction level models of the same design. To ease the work, we propose a correct-by-construction method that automatically and simultaneously generates both fast and accurate transaction level bus models for system simulation. The proposed approach relieves designers from the tedious and error-prone process of refining models and checking for consistency.

This paper proposes a synchronization approach for fast and accu-rate Multi-Core Instruction-Set Simulation (MCISS). An ideal MCISS should run accurately in a real-time fashion. In order to achieve accurate simulation results of MCISS, a lock-step approach, which synchronizes every cycle, is commonly used. However, this approach introduces immense overhead and lowers the simulation speed. Instead of synchronizing every cycle, our approach synchronizes the MCISS based on the data dependency among the simulated programs. Therefore, the synchronization overheads can be highly reduced while the accurate simulation results are ensured. With the proposed approach applied, the simulation speed of MCISS is up to 40 ~ 1,000 million instructions per second (MIPS) in general.

This paper accurately considers wire short defects and proposes an algorithm to guarantee IC chip yield rate improvement for redundant wire insertion. Without considering yield rate degradation caused by shorts, traditional methods may even lead to yield rate loss. However, shorts are more complicated to analyze than opens. Moreover, since any two points of a routed net can be connected by a redundant wire, the number of possible insertion patterns for a chip is un-tractable. To maximize yield rate improvement and to make the problem tractable, we identify a key insight, tolerance-ratio, as an effective guide for choosing insertion patterns and insertion order. Finally, to guarantee yield rate improvement, only positive gain redundant wires are committed. Experimental results show that, compared with unprocessed cases, all yield rate improvements in the proposed algorithm are positive, and the defect rates are reduced by up to 65% and by 24% on average. On the other hand, without considering shorts, the defect rate can increase as much as 7%.

As the advance of high quality displays such as organic light- emitting diode (OLED) or laser TV, the importance of a real-time high dynamic range (HDR) data processing for display devices increases significantly. Many tone mapping algorithms are proposed for rendering HDR images or videos on display screens. The choice of tone mapping algorithm depends on characteristics of displays such as luminance range, contrast ratio and gamma correction. An ideal HDR tone mapping processor should include several tone mapping algorithms and be able to select an appropriate one for different kind of devices and applications. Such a HDR tone mapping processor has characteristics of robust core functionality, high flexibility, and low area consumption. An ARM core based system on chip (SOC) platform with HDR tone mapping ASIC is suitable for such applications. In this paper, we present a systematic methodology to develop an optimized architecture for tone mapping processor in the ARM SOC platform. We illustrate the approach by a HDR tone mapping processor that can handle both photographic and gradient compression. The optimization is achieved through four major steps: common module extraction, computation power enhancement, hardware/software partition and cost function analysis. Based on the proposed scheme, we develop an integrated photographic and gradient compression HDR tone mapping processor that can process 1024times768 images at 60 fps. This design runs at 100 MHz clock and consumes area of 13.8 mm2under TSMC 0.13 mum technology with 50% improvement in speed and area compared with previous results.

An exact zero-skew clock routing algorithm using the Elmore delay model is presented. The results have been verified with accurate waveform simulation. The authors first review a linear time delay computation method. A recursive bottom-up algorithm is then proposed for interconnecting two zero-skewed subtrees to a new tree with zero skew. The algorithm can be applied to single-staged clock trees, multistaged clock trees, and multi-chip system clock trees. The approach is ideal for hierarchical methods of constructing large systems. All subsystems can be constructed in parallel and independently, then interconnected with exact zero skew. Extensions to the routing of optimum nonzero-skew clock trees (for cycle stealing) and multiphased clock trees are also discussed.>

The authors present a clock tree regeneration algorithm for improving both the wirability and performance of VLSI chip designs. After circuit placement, they modify the clock trees originally specified by logic designs utilizing the geometrical information derived from the placement. First, a bipartite bottleneck matching approach is applied to minimize the longest driver to clock pin length. Then a linear assignment approach is used to optimize the total driverpin length. The experimental results are extremely encouraging.>

We propose an efficient circuit placement ap- proach based on analytic net weighting controls for nonlinear performance constraints. We justify the popular net weight- ing heuristic by first showing that an appropriate net weight- ing is a natural result of the Kuhn-Tucker conditions of cir- cuit placement optimization subject to the performance con- straints. We further give a quantitative analysis of the ef- fect of net weighting to wire length change. An effective net weighting control algorithm has been implemented and ap- plied to real chip designs. The results are very promising. A performance-optimized result can be achieved in 13.2 seconds for a chip with 1,403 circuits. An experimental CMOS chip with 45,296 circuits has a complete placement result in 40 minutes while the wire length measure is 20.3 percent better than a simulated annealing approach.

An exact zero skew clock routing algorithm using the Elmore delay model is presented. Recursively in a bottom-up fashion, two zero-skewed subtrees are merged into a new tree with zero skew. The algorithm can be applied to single-staged clock trees, multi-staged clock trees, and multi-chip system clock trees. It is ideal for hierarchical methods of constructing large systems. All subsystems can be constructed in parallel and independently, and then interconnected with exact zero skew. Experimental results are presented.>

An approach to the constraint-based floor planning of flexible, fixed, and preplaced blocks that is based on the removal of redundant constraints and the reshaping of flexible blocks is discussed. A floor plan is said to respect a given constraint set if is satisfies either a vertical or a horizontal constraint in the set for each pair of blocks. The approach presented is to construct a floor plan of optimal area that respects the input constraint set, which is assumed to be derived from a relative placement of the blocks. Reasons for considering this method are delineated, and a heuristic floor-planning algorithm based on constraint reduction and block reshaping is given. A simple example illustrates the algorithm. Several real floor-planning examples are also given.>

The problem considered is that of producing a legal floorplan that respects a given topological constraint set. The floorplanning approach described is targeted for multilayer sea-of-cells based designs. Therefore it is assumed that no channel separations are required between the blocks. The approach can be generalized to incorporate channel separations.>

The authors integrate the concepts and techniques of two existing complementary approaches, namely, the rerouting approach and the top-down hierarchical approach based on linear assignment. This combines and enhances the advantages of the two approaches and results in a fast and high-quality router which can handle large sea-of-gates designs. In addition, it solves the problems of routing interdependence and routing resource estimation which heretofore have not been well addressed yet. The method has been implemented and successfully tested on three real gate-arrays chips: Primary 1, Primary 2, and a channelless industrial example with 100 K gates.>