Browsing by Author "Lai, Bo-Cheng Charles"

Now showing 1 - 20 of 29

A Cache Aware Multithreading Decision Scheme on GPGPUs
(2014-01-01)
Yen, Ta-Kang
;
Yu, Bo-Yao
;
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 on-chip cache hierarchy are the two effective designs to achieve high throughput computing in modern GPGPUs. However, excessive multithreading could aggravate the cache contention while conservative multithreading could leave the execution resource under-utilized. Finding a proper design point between the two has become a significant performance factor to GPGPUs. This paper investigates the correlation between caching behavior and multithreading technique. By demonstrating the trade-off issue between the multithreading and cache contention, this paper proposes a multithreading decision scheme to dynamically adjusts the multithreading degree to achieve superior performance. With the proposed decision scheme, the system performance of memory-intensive workloads can be improved by 60% in average.
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 Hadoop-based Principle Component Analysis on Embedded Heterogeneous Platform
(2017-01-01)
Chen, Sheng-Yen
;
Wei, Chia-I
;
Chiu, Yu-Chen
;
Lai, Bo-Cheng Charles
;
電子工程學系及電子研究所
Hadoop is a widely adopted distributed processing framework which assumes each computing node a CPU-based system with local memory. This design scheme cannot effectively take full advantage of an embedded heterogeneous many-core platform due the mismatch of data collection and management paradigms between the Hadoop environment and embedded heterogeneous systems. This paper proposes a Hadoop-based design of Principle Component Analysis (PCA) to efficiently leverage the distributed embedded heterogeneous many-core systems. By taking the same data layout of conventional Hadoop applications, the proposed design introduces efficient manners to collect and manage the fine-grained data chunks. The experiments on a Tegra K1 has achieved 5.9x performance enhancement.
A High-Performance Double-Layer Counting Bloom Filter for Multicore Systems
(2015-11-01)
Lai, Bo-Cheng Charles
;
Chen, Kuan-Ting
;
Wu, Ping-Ru
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
The snoopy-based protocol is a widely used cache coherence mechanism for a symmetric multiprocessor (SMP) system. However, this broadcast-based protocol blindly disseminates data sharing information across the system, and introduces many unnecessary data operations. This paper proposes a novel architecture of double-layer counting Bloom filter (DLCBF) to reduce the unnecessary data lookups on the local cache and redundant data transactions on the shared interconnection of an SMP system. By adding an extra filtering layer, the DLCBF effectively exploits the data locality of applications. The two-layer hierarchy reduces the storage size of DLCBF by 18.75%, and achieves 81.99% and 31.36% better filtering rates when compared with a classic Bloom filter (BF) and original counting BF, respectively. When applied on the segmented shared bus of an SMP system, the DLCBF outperforms the previous work by 58% for In-filters and 1.86x for Out-filters. This paper also comprehensively explores the key design parameters of DLCBF, including the sizes of top-layer, bottom-layer, and multilayer design. The results show that enlarging the layer filters enhance the filtering rates of DLCBF, while adding an extra filter layer only provides slight benefit.
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 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 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.
An Efficient Hierarchical Banking Structure for Algorithmic Multiported Memory on FPGA
(2017-10-01)
Lai, Bo-Cheng Charles
;
Huang, Kun-Hua
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Algorithmic multiported memory supports concurrent accesses by cooperating block RAMs (BRAMs) with algorithmic operations, and demonstrates the better performance per resource usage on FPGA when compared with register-based designs. However, the current approaches still use significant amount of FPGA resources and pose great design challenges when increasing the access ports. This paper proposes HB-NTX with a resource efficient hierarchical banking structure for nontable-based multi-ported memory design on FPGA. The regular design style enables a systematic flow to scale both read and write ports. When compared with the previous approaches, HB-NTX can reduce 62.03% BRAMs when composing a 2R4W memory with 32K depth. This paper further extends the HB-NTX to alleviate the complexity of the table-based memory designs. When compared with the previous table-based TBLVT approach, the proposed design for a 2R4W memory with 8K depth attains the cost reduction of 39.9%, 14.3%, and 15.6%, for registers, lookup tables, and BRAMs, respectively.
BRAM Efficient Multi-ported Memory on FPGA
(2015)
Lin, Jiun-Liang
;
Lai, Bo-Cheng Charles
;
電機學院
;
電子工程學系及電子研究所
;
College of Electrical and Computer Engineering
Multi-ported memory is broadly used in modern designs on FPGAs. However, the excessive demand on BRAMs to implement multi-ported memory on FPGA would block the usage of BRAMs for other parts of a design. This issue becomes a serious concern especially for designs that require huge internal storage capacity. This paper proposes a BRAM efficient scheme on increasing read ports and write ports. When compared with previous works, the proposed multi-ported memory can reduce up to 53% requirement on BRAMs with only minor frequency 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.
Classifier Grouping to Enhance Data Locality for A Multi-Threaded Object Detection Algorithm
(2011)
Lai, Bo-Cheng Charles
;
Chiang, Chih-Hsuan
;
Li, Guan-Ru
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Object detection has become an enabling function for modern smart embedded devices to perform intelligent applications and interact with the environment appropriately and promptly. However, the limited computation resource of embedded devices has become a barrier to execute the computation intensive object detection algorithm. Leveraging the multi-threading scheme on embedded multi-core systems provides an opportunity to boost the performance. However, the memory bottleneck limits the performance scalability. Improving data locality of applications and maximizing the data reuse for on-chip caches have therefore become critical design concerns. This paper comprehensively analyzes the memory behavior and data locality of a multi-threaded object detection algorithm. A novel Classifier-Grouping scheme is proposed to significantly enhance the data reuse for on-chip caches of embedded multi-core systems. By executing a multi-threaded object detection algorithm on a cycle-accurate multi-core simulator, the proposed approach can achieve up to 62% better performance when compared with the original parallel program.
Computation and Communication Aware Task Graph Scheduling on Multi-GPU Systems
(2015)
Wang, Yun-Ting
;
Lee, Jia-Ying
;
Lai, Bo-Cheng Charles
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
GPUs have emerged as popular throughput computing platforms due to the massively parallel computing capability and low cost. To attain further performance enhancement beyond single GPU, there is a growing interest in exploiting systems with multiple GPUs. Attaining superior performance in a multi-GPU system involves three main design challenges, namely load balance, memory utilization, and data transfer. Imbalanced loading across a system could cause idling of GPUs while poor data reuse would trigger excessive memory accesses. The inefficient data transfer between a host and a device becomes a considerable performance overhead during high throughput computing. This paper aims at addressing the above design issues by proposing a Computation and Communication Aware task graph Scheduling (CCAS) for multi-GPU systems. The proposed scheduling approach (CCAS) adopts an effective heuristic algorithm that considers both data reuse and load balance in a multi-GPU system. The data transfer overhead is hidden by extensively overlapping computation and data communication. The experimental results of the proposed CCAS have demonstrated an average of 22.15% performance enhancement when compared with a previous work.
Design of Application Specific Throughput Processor for Matrix Operations
(2015)
Wu, Ping-Ju
;
Lin, Chien-Yu
;
Lai, Bo-Cheng Charles
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
In modern computation routines, matrix operations are broadly used in many scientific realms, ranging from high performance supercomputers to resource constrained embedded devices. Previous studies have revealed that the computation efficiency of matrix operations is significantly determined by the data accesses behavior of the computation platform. This paper introduces an integrated multicore system, including software stacks and hardware modules that can accelerate matrix operations and reduce data access overhead. With the proposed hardware module, the performance of our multicore embedded platform can improve up to 24.09%. Besides the hardware design, we also develop a framework that can facilitate the prototyping of embedded system designs, including functional verification of hardware modules as well as co-simulation with high level OpenCL language.
Efficient Designs of Multiported Memory on FPGA
(2017-01)
Lai, Bo-Cheng Charles
;
Lin, Jiun-Liang
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
The utilization of block RAMs (BRAMs) is a critical performance factor for multiported memory designs on field-programmable gate arrays (FPGAs). Not only does the excessive demand on BRAMs block the usage of BRAMs from other parts of a design, but the complex routing between BRAMs and logic also limits the operating frequency. This paper first introduces a brand new perspective and a more efficient way of using a conventional two reads one write (2R1W) memory as a 2R1W/4R memory. By exploiting the 2R1W/4R as the building block, this paper introduces a hierarchical design of 4R1W memory that requires 25% fewer BRAMs than the previous approach of duplicating the 2R1W module. Memories with more read/write ports can be extended from the proposed 2R1W/4R memory and the hierarchical 4R1W memory. Compared with previous xor-based and live value table-based approaches, the proposed designs can, respectively, reduce up to 53% and 69% of BRAM usage for 4R2W memory designs with 8K-depth. For complex multiported designs, the proposed BRAM-efficient approaches can achieve higher clock frequencies by alleviating the complex routing in an FPGA. For 4R3W memory with 8K-depth, the proposed design can save 53% of BRAMs and enhance the operating frequency by 20%.
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.