Browsing by Author "Kuo, Hsien-Kai"

Now showing 1 - 14 of 14

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 Distributed Thread Scheduler for Dynamic Multithreading on Throughput Processors
(2013)
Yen, Ta-Kan
;
Kuo, Hsien-Kai
;
Lai, Bo-Cheng Charles
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
GPGPUs have emerged as one of the most widely used throughput processors. Deep multithreading and cache hierarchy are the two effective implementations to achieve high throughput computing in modern GPGPUs. However, these are two conflicting design options. Finding a proper design point between the two has become a significant performance factor to GPGPUs. This paper proposes a distributed thread scheduler for dynamic multithreading on GPGPUs. By demonstrating the trade-off issue between the multithreading and cache contention, the proposed scheduler dynamically adjusts the multithreading degree to achieve superior performance. With the proposed scheduler, the cache misses can be decreased by 20.6% and 37.9% on the L1 and L2 cache respectively. The overall performance can be enhanced by an average of 16.4%.
A Distributed Thread Scheduler for Dynamic Multithreading on Throughput Processors
(2013-01-01)
Yen, Ta-Kan
;
Kuo, Hsien-Kai
;
Lai, Bo-Cheng Charles
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
GPGPUs have emerged as one of the most widely used throughput processors. Deep multithreading and cache hierarchy are the two effective implementations to achieve high throughput computing in modern GPGPUs. However, these are two conflicting design options. Finding a proper design point between the two has become a significant performance factor to GPGPUs. This paper proposes a distributed thread scheduler for dynamic multithreading on GPGPUs. By demonstrating the trade-off issue between the multithreading and cache contention, the proposed scheduler dynamically adjusts the multithreading degree to achieve superior performance. With the proposed scheduler, the cache misses can be decreased by 20.6% and 37.9% on the L1 and L2 cache respectively. The overall performance can be enhanced by an average of 16.4%.
A Highly Parallel Design for Irregular LDPC Decoding on GPGPUs
(2012)
Chiu, Tsou-Han
;
Kuo, Hsien-Kai
;
Lai, Bo-Cheng Charles
;
交大名義發表
;
National Chiao Tung University
Low-Density Parity-Check (LDPC) code is a powerful error correcting code. It has been widely adopted by many communication systems. Finding a fast and efficient design of LDPC has been an active research area. This paper proposes a high performance design for irregular LDPC decoding on a general purpose graphic processing unit (GPGPU). A GPGPU is a many-core architecture which enables massively parallel computing. In this paper, a high degree of computation parallelism has been exposed by decoding multiple LDPC code-words concurrently. An innovative data structure is proposed to more efficiently leverage memory coalescing for the irregular data accesses of LDPC decoding. Data spatial locality is maximized by keeping more reusable data within the on-chip cache of a GPGPU. The data communication overhead between a host and a GPGPU is minimized through a single word copy for the convergence check. The experiment results show that the proposed design can achieve up to 55.68X runtime improvement, when compared with a sequential LDPC program on a CPU.
A Locality-Aware Dynamic Thread Scheduler for GPGPUs
(2013-01-01)
Huang, Yu-Hao
;
Tseng, Ying-Yu
;
Kuo, Hsien-Kai
;
Yen, Ta-Kan
;
Lai, Bo-Cheng Charles
Modern GPGPUs implement on-chip shared cache to better exploit the data reuse of various general purpose applications. Given the massive amount of concurrent threads in a GPGPU, striking the balance between Data Locality and Load Balance has become a critical design concern. To achieve the best performance, the trade-off between these two factors needs to be performed concurrently. This paper proposes a dynamic thread scheduler which co-optimizes both the data locality and load balance on a GPGPU. The proposed approach is evaluated using three applications with various input datasets. The results show that the proposed approach reduces the overall execution cycles by up to 16% when compared with other approaches concerning only one objective.
A Quantitative Method to Data Reuse Patterns of SIMT Applications
(2016-07-12)
Lai, Bo-Cheng Charles
;
Platero, Luis Garrido
;
Kuo, Hsien-Kai
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Understanding data reuse patterns of a computing system is crucial to effective design optimization. The emerging Single Instruction Multiple Threads (SIMT) processor adopts a programming model that is fundamentally disparate from conventional scalar processors. There is a lack of analytical approaches to quantify the data reuse of SIMT applications. This paper presents a quantitative method to study the data reuse inherent to SIMT applications. A metric, Data Reuse Degree, is defined to measure the amount of reused data between memory references, and associate each data reuse degree to a temporal distance representing the virtual time of the execution process. The experiments are performed on an abstracted SIMT processor that considers the programming model and runtime specifics. The experiments illustrate diverse data reuse patterns of SIMT applications and explore the impacts of architectural limitations.
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.
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.
Enhancing Data Reuse in Cache Contention Aware Thread Scheduling on GPGPU
(2016)
Lu, Chin-Fu
;
Kuo, Hsien-Kai
;
Lai, Bo-Cheng Charles
;
交大名義發表
;
National Chiao Tung University
GPGPUs have been widely adopted as throughput processing platforms for modern big-data and cloud computing. Attaining a high performance design on a GPGPU requires careful tradeoffs among various design concerns. Data reuse, cache contention, and thread level parallelism, have been demonstrated as three imperative performance factors for a GPGPU. The correlated performance impacts of these factors pose non-trivial concerns when scheduling threads on GPGPUs. This paper proposes a three-staged scheduling scheme to co-schedule the threads with consideration of the three factors. The experiment results on a set of irregular parallel applications, when compared with previous approaches, have demonstrated up to 70% execution time improvement.
FDPrior: A Force-Directed Based Parallel Partitioning Algorithm for Three Dimensional Integrated Circuits on GPGPU
(2011)
Chen, Wan-Jing
;
Kuo, Hsien-Kai
;
Chiu, Tsou-Han
;
Lai, Bo-Cheng Charles
;
電子工程學系及電子研究所
This paper proposes an innovative force-directed parallel algorithm, FDPrior, to solve the multilayer partitioning problem of 3DICs. The growing scale and multi-layered structure of the 3DIC technology make it computational expensive for EDA tools to achieve optimization goals. Exploiting the algorithmic parallelism on multi-core architectures becomes the key to attain scalable runtime. By adopting the N-body simulation scheme and novel techniques to reduce synchronization overhead, FDPrior successfully exposes the massive parallelism on the multi-core GPGPU architecture. The objective is to minimize the total number of Through Silicon Vias (TSVs) while meeting the area constraint for each layer. The experimental results on ISPD98 benchmark show that FDPrior outperforms the conventional FM algorithm by achieving in average 5.0X better TSVs and up to 247.3X runtime speedup. Compared with PP3D, a parallel 3DIC partitioning algorithm, FDPrior achieves 6.7X better TSVS with 3.3 X runtime enhancement.
MEMORY CAPACITY AWARE NON-BLOCKING DATA TRANSFER ON GPGPU
(2013)
Liu, Hao-Wei
;
Kuo, Hsien-Kai
;
Chen, Kuan-Ting
;
Lai, Bo-Cheng Charles
;
電子工程學系及電子研究所
The massive data demand of GPGPUs requires expensive memory modules, such as GDDR, to support high data bandwidth. The high cost poses constraints on the total memory capacity available to GPGPUs, and the data need to be transferred between the host CPUs and GPGPUs. However, the long latency of data transfers has resulted in significant performance overhead. To alleviate this issue, the modern GPGPUs have implemented the non-blocking data transfer allowing a GPGPU to perform computing while the data is being transmitted. This paper proposes a capacity aware scheduling algorithm that exploits the non-blocking data transfer in modern GPGPUs. By effectively taking the advantage of non-blocking transfers, experiment results demonstrate an average of 24.01% performance improvement when compared to existing approaches that only consider memory capacity.
Reducing Contention in Shared Last-Level Cache for Throughput Processors
(2014-11-01)
Kuo, Hsien-Kai
;
Lai, Bo-Cheng Charles
;
Jou, Jing-Yang
;
交大名義發表
;
National Chiao Tung University
Deploying the Shared Last-Level Cache (SLLC) is an effective way to alleviate the memory bottleneck in modern throughput processors, such as GPGPUs. A commonly used scheduling policy of throughput processors is to render the maximum possible thread-level parallelism. However, this greedy policy usually causes serious cache contention on the SLLC and significantly degrades the system performance. It is therefore a critical performance factor that the thread scheduling of a throughput processor performs a careful trade-off between the thread-level parallelism and cache contention. This article characterizes and analyzes the performance impact of cache contention in the SLLC of throughput processors. Based on the analyses and findings of cache contention and its performance pitfalls, this article formally formulates the aggregate working-set-size-constrained thread scheduling problem that constrains the aggregate working-set size on concurrent threads. With a proof to be NP-hard, this article has integrated a series of algorithms to minimize the cache contention and enhance the overall system performance on GPGPUs. The simulation results on NVIDIA\'s Fermi architecture have shown that the proposed thread scheduling scheme achieves up to 61.6% execution time enhancement over a widely used thread clustering scheme. When compared to the state-of-the-art technique that exploits the data reuse of applications, the improvement on execution time can reach 47.4%. Notably, the execution time improvement of the proposed thread scheduling scheme is only 2.6% from an exhaustive searching scheme.
Thread Affinity Mapping for Irregular Data Access on Shared Cache GPGPU
(2012)
Kuo, Hsien-Kai
;
Chen, Kuan-Ting
;
Lai, Bo-Cheng Charles
;
Jou, Jing-Yang
;
電子工程學系及電子研究所
Memory Coalescing and on-chip shared Cache are two effective techniques to alleviate the memory bottleneck in modern GPGPUs. These two techniques are very useful on applications with regular memory accesses. However, they become ineffective on concurrent threads with large numbers of uncoordinated accesses and the potential performance benefit could be significantly degraded. This paper proposes a thread affinity mapping methodology to coordinate the irregular data accesses on shared cache GPGPUs. Based on the proposed affinity metrics, threads are congregated into execution groups which are able to fully exploit the memory coalescing and data sharing within an application. An average of 3.5x runtime speedup is achieved on a Fermi GPGPU. The speedup scales with the sizes of test cases, which makes the proposed methodology an effective and promising solution for the continually increasing complexities of applications in the future many-core systems.
Unified Designs for High Performance LDPC Decoding on GPGPU
(2016-12-01)
Lai, Bo-Cheng Charles
;
Lee, Chia-Ying
;
Chiu, Tsou-Han
;
Kuo, Hsien-Kai
;
Chang, Chun-Kai
Modern GPGPU\'s have enabled massively parallel computing with programmability that can exploit the highly parallel nature of LDPC decoding. Previous works customized the design on a GPGPU towards specific execution attributes of a particular LDPC decoding matrix. Supporting different LDPC decoding matrices requires either substantial rework on the current program, or a brand new parallel design. This paper proposes two unified designs that can achieve high performance for both regular and irregular LDPC decoding on a GPGPU. The first design introduces a node-based scheme with a versatile translation array mechanism that can efficiently handle the complex data access patterns of different LDPC decoding matrices. The second design proposes an edge-based parallel paradigm that uses more intuitive data layout. More edges than nodes in a Tanner graph also give the edge-based design higher computation parallelism when there are limited concurrent codewords. With the proposed unified designs, designers can be ignorant of the types of LDPC matrices and achieve high performance LDPC decoding. The experiments on a GTX 470 GPGPU have demonstrated up to 134.56x runtime improvement, when compared with designs on a high-end CPU. The maximum throughput can reach 80.25 Mbps. When compared with the previous customized designs, the proposed systematic designs can reach better performance while relieving the effort of customization.