Browsing by Author "Jou, Jing-Yang"

Now showing 1 - 20 of 40

A Cache Hierarchy Aware Thread Mapping Methodology for GPGPUs
(2015-04-01)
Lai, Bo-Cheng Charles
;
Kuo, Hsien-Kai
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
The recently proposed GPGPU architecture has added a multi-level hierarchy of shared cache to better exploit the data locality of general purpose applications. The GPGPU design philosophy allocates most of the chip area to processing cores, and thus results in a relatively small cache shared by a large number of cores when compared with conventional multi-core CPUs. Applying a proper thread mapping scheme is crucial for gaining from constructive cache sharing and avoiding resource contention among thousands of threads. However, due to the significant differences on architectures and programming models, the existing thread mapping approaches for multi-core CPUs do not perform as effective on GPGPUs. This paper proposes a formal model to capture both the characteristics of threads as well as the cache sharing behavior of multi-level shared cache. With appropriate proofs, the model forms a solid theoretical foundation beneath the proposed cache hierarchy aware thread mapping methodology for multi-level shared cache GPGPUs. The experiments reveal that the three-staged thread mapping methodology can successfully improve the data reuse on each cache level of GPGPUs and achieve an average of 2.3 x to 4.3 x runtime enhancement when compared with existing approaches.
A code generation algorithm of crosstalk-avoidance code with memory for low-power on-chip bus
(2008)
Cheng, Kuang-Chin
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
In this paper, a bus encoding approach including related code generation algorithm for global data busses is developed to produce area-efficient crosstalk-avoidance (CA) codes with considering low-power requirements. Proposed codes are codes with memory using overlapping boundary strategy. The probabilistic distribution of input data could be included to reduce the power consumption. The performance improvement of CA codes is nearly 2x for heavily coupled busses based on theoretical analysis. As compared to uncoded datawords, proposed codes show 12% to 38% energy-reduction on bus for an equi-probable 32-bit bus design.
A Formal Method to Improve SystemVerilog Functional Coverage
(2012-01-01)
Cheng, An-Che
;
Yen, Chia-Chih
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Improving functional coverage efficiently in a verification environment based on constrained random simulation could be a difficult task, since some design states are hard to be reached by random input patterns. On the other hand, manually crafting direct test patterns may be time consuming. In this paper, a functional test pattern generation (FTPG) framework is proposed to automatically produce deterministic test patterns for complete coverage. The framework is based on the functional coverage model (covergroup) provided by SystemVerilog, and it could be easily integrated to modern digital design flow. We synthesize a practical subset of covergroup language constructs to enable FTPG by a SAT-solver. An algorithm called MRRS is proposed to minimize the potential large complexity of the synthesized circuits. Preliminary experimental results demonstrate that MRRS could facilitate FTPG to achieve 43X speed-up in average while the maximum speed-up can reach 67X. To the best of our knowledge, this is the first paper which proposes an FTPG method that utilizes covergroups.
A Learning-on-Cloud Power Management Policy for Smart Devices
(2014)
Pan, Gung-Yu
;
Lai, Bo-Cheng Charles
;
Chen, Sheng-Yen
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
Energy consumption poses severe limitations for smart devices, urging the development of effective and efficient power management policies. State-of-the-art learning-based policies are autonomous and adaptive to the environment, but they are subject to costly computational overhead and lengthy convergence time. As smart devices are connected to Internet, this paper proposes the Learning-on-Cloud (LoC) policy to exploit cloud computing for power management. Sophisticated learning engines are offloaded from local devices to the cloud with minimal communication data, thus the runtime overhead is reduced. The learning data are shared between many devices with the same model, hence the convergence rate is raised. With one thousand devices connecting to the cloud, the LoC agent is able to converge within a few iterations; the energy saving is better than both of the greedy and the learning-based policies with less latency penalty. By implementing the LoC policy as an Android App, the measured overhead is only 0.01% of the system time.
A precise bandwidth control arbitration algorithm for hard real-time SoC buses
(2007)
Lin, Bu-Ching
;
Lee, Geeng-Wei
;
Huang, Juinn-Dar
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
On an SoC bus, contentions occur while different IP cores request the bus access at the same time. Hence an arbiter is mandatory to deal with the contention issue on a shared bus system. In different applications, IPs may have real-time and/or bandwidth requirements. It is very difficult to design an arbitration algorithm to simultaneously meet these two requirements. In this paper, we propose an innovative arbitration algorithm, RB-lottery, to meet both of the requirements. It can provide not only the hard real-time guarantee but also the precise bandwidth controllability. The experimental results show that RB-lottery outperforms several well-known existing arbitration algorithms.
A Read-Write Aware DRAM Scheduling for Power Reduction in Multi-Core Systems
(2014-01-01)
Lai, Chih-Yen
;
Pan, Gung-Yu
;
Kuo, Hsien-Kai
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
The demand of high performance and low power has increased the importance of power efficiency in multi-core systems. In modern multi-core architectures, DRAM has dominated the power consumption and therefore reordering based DRAM scheduling has been intensively studied to reduce the power. However, the benefit of reordering is not fully explored by the previous studies. To further reduce the power, this paper proposes the read-write reordering and the read-write aware throttling. When compared to the existing work, the proposed techniques reduce 10% more DRAM power with less performance degradation.
A real-time and bandwidth guaranteed arbitration algorithm for SoC bus communication
(2006)
Chen, Chien-Hua
;
Lee, Geeng-Wei
;
Huang, Juinn-Dar
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
In shared SoC bus systems, arbiters are usually adopted to solve bus contentions with various kinds of arbitration algorithms. We propose an arbitration algorithm, RT lottery, which is designed to meet both hard real-time and bandwidth requirements. For fast evaluation and exploration, we use high abstract-level models in our system simulation environment to generate parameters for our configurable arbiter. The experimental results show that RT-lottery can meet all hard real-time requirements and perform very well in bandwidth allocation. The results also show that RT-lottery outperforms several commonly-used arbitration algorithms today.
A tableless approach for high-level power modeling using neural networks
(2007-01-01)
Hsu, Chih-Yang
;
Hsieh, Wen-Tsan
;
Liu, Chien-Nan Jimmy
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
For complex digital circuits, building their power models is a popular approach to estimate their power consumption without detailed circuit information. In the literature, most of power models have to increase their complexity in order to meet the accuracy requirement. In this paper, we propose a tableless power model for complex circuits that uses neural networks to learn the relationship between power dissipation and input/output signal statistics. The complexity of our neural power model has almost no relationship with circuit size and number of inputs and outputs such that this power model can be kept very small even for complex circuits. Using such a simple structure, the neural power models can still have high accuracy because they can automatically consider the non-linear characteristic of power distributions and the effects of both state-dependent leakage power and transition-dependent switching power. The experimental results have shown the accuracy and efficiency of our approach on benchmark circuits and one practical design for different test sequences with wide range of input distributions.
Accelerating Dynamic Peak Power Analysis Using An Essential-Signal-Based Methodology
(2011)
Shih, Che-Hua
;
Yen, Chia-Chih
;
Lin, Shen-Tien
;
Lin, Hermes
;
Jou, Jing-Yang
Accurate peak power measurement requires detailed switching and delay information for each signal over the entire simulation. Performing a full signal dump and power calculation for a long simulation run usually spends a large amount of time and disk space. In this paper, we propose an Essential-signal-based methodology which only performs power analysis over a small subset of the original simulation but still acquires the true peak power value. Experimental results show that the proposed methodology significantly decreases both time (about 18 X speedup) and disk space usage (about 87% reduction) against the traditional power analysis flow.
Accurate Rank Ordering of Error Candidates for Efficient HDL Design Debugging
(2009-02-01)
Jiang, Tai-Ying
;
Liu, Chien-Nan Jimmy
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
When hardware description languages (HDLs) are used in describing the behavior of a digital circuit, design errors (or bugs) almost inevitably appear in the HDL code of the circuit. Existing approaches attempt to reduce efforts involved in this debugging process by extracting a reduced set of error candidates. However, the derived set can still contain many error candidates, and finding true design errors among the candidates in the set may still consume much valuable time. A debugging priority method [21] was proposed to speed up the error-searching process in the derived error candidate set. The idea is to display error candidates in an order that corresponds to an individual's degree of suspicion. With this method, error candidates are placed in a rank order based on their probability of being an error. The more likely an error candidate is, a design error (or a bug), the higher the rank order that it has. With the displayed rank order, circuit designers should find design errors quicker than with blind searching when searching for design errors among all the derived candidates. However, the currently used confidence score (CS) for deriving the debugging priority has some flaws in estimating the likelihood of correctness of error candidates due to the masking error situation. This reduces the degree of accuracy in establishing a debugging priority. Therefore, the objective of this work is to develop a new probabilistic confidence score (PCS) that takes the masking error situation into consideration in order to provide a more reliable and accurate debugging priority. The experimental results show that our proposed PCS achieves better results in estimating the likelihood of correctness and can indeed suggest a debugging priority with better accuracy, as compared to the CS.
An observability measure to enhance statement coverage metric for proper evaluation of verification completeness
(2005)
Jiang, Tai-Ying
;
Liu, Chien-Nan Jimmy
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Simulation based validation approaches are still the primary workhorse for solving the verification problem of getting the initial HDL description correct, especially for large scaled designs. However, most of existing code coverage metrics do not address obsevability issue [2]. Therefore, we intend to provide additional observability measures to statement coverage metric for more proper and realistic evaluation of verification completeness for a HDL design. As compared to OCCOM [1,2,3], our approach estimates a real probabilistic likelihood of propagating erroneous effects without any unreasonable assumptions and can always provide lower bound estimation.
An optimum algorithm for compacting error traces for efficient design error debugging
(2006-11-01)
Yen, Chia-Chih
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Diagnosing counterexamples with error traces has acted as one of the most critical steps in functional verification. Unfortunately, error traces are normally very lengthy such that designers need to spend considerable effort to understand them. To alleviate the designers' burden for debugging, we present a SAT-based algorithm for reducing the lengths of error traces. The algorithm performs the paradigm of the binary search algorithm to halve the search space recursively. Furthermore, it applies a novel theorem to guarantee gaining the shortest lengths for the error traces. Based on the optimum algorithm, we develop two robust heuristics to handle real designs. Experimental results demonstrate that our approaches greatly surpass previous work and, indeed, have promising solutions.
Cache Capacity Aware Thread Scheduling for Irregular Memory Access on Many-Core GPGPUs
(2013-01-01)
Kuo, Hsien-Kai
;
Yen, Ta-Kan
;
Lai, Bo-Cheng Charles
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
On-chip shared cache is effective to alleviate the memory bottleneck in modern many-core systems, such as GPGPUs. However, when scheduling numerous concurrent threads on a GPGPU, a cache capacity agnostic scheduling scheme could lead to severe cache contention among threads and thus significant performance degradation. Moreover, the diverse working sets in irregular applications make the cache contention issue an even more serious problem. As a result, taking cache capacity into account has become a critical scheduling issue of GPGPUs. This paper formulates a Cache Capacity Aware Thread Scheduling Problem to capture the impact of cache capacity as well as different architectural considerations. With a proof to be NP-hard, this paper has proposed two algorithms to perform the cache capacity aware thread scheduling. The simulation results scheduling scheme can effectively avoid cache contention, and achieve an average of 44.7% cache miss reduction and 28.5% runtime enhancement. The paper also shows the runtime can be enhanced up to 62.5% for more complex applications.
Chain-Based Pin Count Minimization for General-Purpose Digital Microfluidic Biochips
(2016)
Lei, Yung-Chun
;
Hsu, Chen-Shing
;
Huang, Juinn-Dar
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
Minimizing the number of external control pins is one of the most important optimization objectives in digital microfluidic biochip (DMFB) designs especially as the chip size gets even bigger. So far, only few works focus on this issue for general-purpose DMFBs. In this paper, we present a pin count minimization algorithm based on sophisticated electrode chaining on regular or irregular electrode arrays. The key idea of the proposed method is that actuation information can be implied from previous neighborhood electrodes to later ones throughout a chain. Experimental results show that the pin count reduction can be near 50% in large DMFBs.
Communication-driven task binding for multiprocessor with latency insensitive Network-on-Chip
(2005)
Lin, Liang-Yu
;
Wang, Cheng-Yeh
;
Huang, Pao-Jui
;
Chou, Chih-Chieh
;
Jou, Jing-Yang
Network-on-Chip is a new design paradigm for designing core based System-on-Chip. It features high degree of reusability and scalability. In this paper, we propose a switch which employs the latency insensitive concepts and applies the round-robin scheduling techniques to achieve high communication resource utilization. Based on the assumptions of the 2D-mesh network topology constructed by the switch, this work not only models the communication and the contention effect of the network, but develops a communication-driven task binding algorithm that employs the divide and conquer strategy to map applications onto the multiprocessor system-on-chip. The algorithm attempts to derive a binding of tasks such that the overall system throughput is maximized. To compare with the task binding without consideration of communication and contention effect, the experimental results demonstrate that the overall improvement of the system throughput is 20% for 844 test cases.
Design-for-Debug Layout Adjustment for FIB Probing and Circuit Editing
(2011)
Chen, Kuo-An
;
Chang, Tsung-Wei
;
Wu, Meng-Chen
;
Chao, Mango C. -T.
;
Jou, Jing-Yang
While the technology node continually and aggressively scales, the resolution of FIB techniques does not scale as fast. Thus, the percentage of nets which can be observed or repaired through FIB probing or circuit editing is significantly decreased for advanced process technologies, which limits the candidates that can be physically examined through the FIB techniques during the debugging process. This paper introduces a design-for-debug framework which can adjust the layout to increase the FIB observable rate and the FIB repairable rate for its signals. The layout adjustment is made through pre-defined simple operations subject to the design rules and the timing constraints. Hence, the proposed framework does not require a complicated router as its core and can be applied in conjunction with any commercial APR tool. The experimental result based on an 90nm technology has demonstrated that the proposed DFD framework can effectively increase the FIB observable and repairable rates under different parameter settings while the overall area and circuit performance remain the same.
Efficient Coverage-Driven Stimulus Generation Using Simultaneous SAT Solving, with Application to SystemVerilog
(2014-11-01)
Cheng, An-Che
;
Yen, Chia-Chih (Jack)
;
Val, Celina G.
;
Bayless, Sam
;
Hu, Alan J.
SystemVerilog provides powerful language constructs for verification, and one of them is the covergroup functional coverage model. This model is designed as a complement to assertion verification, that is, it has the advantage of defining cross-coverage over multiple coverage points. In this article, a coverage-driven verification (CDV) approach is formulated as a simultaneous Boolean satisfiability (SAT) problem that is based on covergroups. The coverage bins defined by the functional model are converted into Conjunction Normal Form (CNF) and then solved together by our proposed simultaneous SAT algorithm PLNSAT to generate stimuli for improving coverage. The basic PLNSAT algorithm is then extended in our second proposed algorithm GPLNSAT, which exploits additional information gleaned from the structure of SystemVerilog covergroups. Compared to generating stimuli separately, the simultaneous SAT approaches can share learned knowledge across each coverage target, thus reducing the overall solving time drastically. Experimental results on a UART circuit and the largest ITC benchmark circuits show that the proposed algorithms can achieve 10.8x speedup on average and outperform state-of-the-art techniques in most of the benchmarks.
Equivalence Checking of Scheduling with Speculative Code Transformations in High-Level Synthesis
(2011)
Lee, Chi-Hui
;
Shih, Che-Hua
;
Huang, Juinn-Dar
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
This paper presents a formal method for equivalence checking between the descriptions before and after scheduling in high-level synthesis (HLS). Both descriptions are represented by finite state machine with datapaths (FSMDs) and are then characterized through finite sets of paths. The main target of our proposed method is to verify scheduling employing code transformations - such as speculation and common subexpression extraction (CSE), across basic block (BB) boundaries - which have not been properly addressed in the past. Nevertheless, our method can verify typical BB-based and path-based scheduling as well. The experimental results demonstrate that the proposed method can indeed outperform an existing state-of-the-art equivalence checking algorithm.
Fine-grained bandwidth control arbiter and the method thereof
(2008-08-28)
Huang, Juinn-Dar
;
Lin, Bu-Ching
;
Lee, Geeng-Wei
;
Jou, Jing-Yang
A fine-grained bandwidth control arbiter manages the shared bus usage of the requests of the masters which have real-time and/or bandwidth requirements, moreover, the masters are preset a ticket respectively. The arbiter consists of three components, a real-time handler, a bandwidth regulator, and a lottery manager with tuned weight. The real-time handler grants the most urgent request. The bandwidth regulator handles the bandwidth allocation and blocks the requests of masters that have met the bandwidth requirement. The lottery manager with tuned weight stochastically grants one of the contending masters according to the ticket assignment.
FSM-Based Formal Compliance Verification of Interface Protocols
(2010-09-01)
Shih, Che-Hua
;
Yang, Ya-Ching
;
Yen, Chia-Chih
;
Huang, Juinn-Dar
;
Jou, Jing-Yang
Verifying whether a building block conforms to a specific interface protocol is one of the important steps in a platform-based system-on-a-chip design methodology. There are limitations for most of the existing methods for interface protocol compliance verification. Simulation-based methods have the false positive problem while formal property checking methods may suffer from memory explosion and excessive runtime. In this paper, we propose a novel approach for interface protocol compliance verification. The properties of the interface protocol are first specified as a specification FSM. Then the compliance of interface logic is formally verified at the higher FSM level so that the required memory and runtime can be greatly reduced. Finally, it is shown theoretically and experimentally that the proposed algorithm possesses acceptably low time complexity for practical applications.