Browsing by Author "Pean, DL"

Now showing 1 - 9 of 9

A release combined scheduling scheme for non-uniform dependence loops
(2002-03-01)
Pean, DL
;
Chua, HT
;
Chen, C
;
資訊工程學系
;
Department of Computer Science
In general, synchronization mechanisms can be used to preserve dependence constraints in any nested loop, and can be combined with a loop scheduling scheme to form a uniform framework to obtain the correct execution order and balance workload distribution. Most current scheduling mechanisms cannot handle non-uniform dependence loops. In this paper, we propose a new combined scheduling scheme called Release Combined Scheduling for Non-uniform Dependence Loops (RCS) to schedule non-uniform dependence doubly-nested loops in multiprocessor systems. It combines both static and dynamic scheduling mechanisms in order to optimize the system performance. In our approach, initialisation of a set of scheduling information is based on the concept of the minimum dependence distance. During runtime, scheduling information is used to adjust the number of parallelizable iterations. Our method is able to discover more parallelism from a given non-uniform dependence doubly-nested loop than is possible with previous approaches. The experimental results show that the RCS method reliably exploits parallelism and outperforms most of the existing non-uniform dependence loop scheduling schemes by 20.29%, on average.
An optimized dependence convex hull partitioning technique to maximize parallelism of nested loops with non-uniform dependences
(2000)
Pean, DL
;
Lai, GJ
;
Chen, C
;
資訊工程學系
;
Department of Computer Science
There are many methods existing for nested loop partitioning; however most of them perform poorly when partitioning loops with non-uniform dependences. This paper proposes a generalized and optimized loop partitioning mechanism to exploit parallelism from nested loops with non-uniform dependences. Our approach based on the dependence convex theory will divide the loop into variable size partitions. Furthermore, the proposed algorithm partitions a nested loop by using the copy-renaming and the optimized partitioning techniques to minimize the number of parallel regions of the iteration space, outperforming the other previous partition mechanisms of nested loops with non-uniform dependences.
An optimized three region partitioning technique to maximize parallelism of nested loops with non-uniform dependences
(2001-05-01)
Pean, DL
;
Chen, C
;
資訊工程學系
;
Department of Computer Science
There are many methods for nested loop partitioning exist: however. most of them perform poorly when they partition loops with non-uniform dependences. This paper proposes a generalized and optimized loop partitioning mechanism which can exploit parallelism in nested loops with non-uniform dependences. Our approach based on the region partitioning technique divides the loop into variable size partitions. Furthermore, the proposed algorithm partitions a nested loop using the copy-renaming and optimized partitioning techniques so as to minimize the serial part of the iteration space. Thus, it out performs previous partition mechanisms for nested loops with non-uniform dependences. Compared with other popular techniques, our scheme shows dramatic improve ment in preliminary performance results.
Design of a scalable multiprocessor architecture and its simulation
(2001-09-01)
Pean, DL
;
Wu, CC
;
Chua, HT
;
Chen, C
;
資訊工程學系
Performance enhancement and system scalability are two of the most important issues in the design of multiprocessor systems. A scalable cluster-based multiprocessor architecture and its simulation environment called SEECMA are proposed. Several new issues in our architecture, including scalable cache coherence protocols, relaxed memory consistency models, memory optimization techniques and several types of processors are considered. It has been developed to meet current trends in clustering architecture design. Additionally, the SEECMA environment is presented as a helpful investigation tool for both education and research. In addition to many simulation options. it is provided with a user-friendly graphic interface. SEECMA can automatically collect data from several simulation runs and display the results for comparison. So far. we have evaluated several vital issues of cluster-based multiprocessors on SEECMA including effective prefetching and replacement policies, and optimization of migratory sharing using both hardware and software mechanisms. On average, these enhance system performance by up to 8%, 9%, and 7%. respectively. Our cluster-based multiprocessor architecture also scales more readily than the current general, or cluster-based, multiprocessor environments. (C) 2001 Elsevier Science Inc. All rights reserved.
Effective mechanisms to reduce the overhead of migratory sharing for linked-based cache coherence protocols in clustering multiprocessor architecture
(1998)
Pean, DL
;
Wu, JR
;
Chen, C
;
資訊工程學系
;
Department of Computer Science
Migratory-sharing data references will incur many cache misses that can be reduced by merging the invalidation/update requests and the cache misses. This paper presents effective software and hardware techniques to reduce the overhead of migratory-sharing references for the linked-based cache coherence protocols. The software scheme combines both compiler labeling and run time detection techniques. The hardware scheme uses the special access patterns in the linked-based protocols to detect migratory data objects. We have evaluated the performance on the linked-based program-driven simulation environment by using a set of SPLASH benchmarks. According to the simulation results, our software and hm du are methods effectively enhanced the system performance up to 29% and 23% respectively by reducing the overhead of the migratory-sharing references.
Effective parallelization techniques for non-uniform loops
(1998)
Pean, DL
;
Wu, CC
;
Chua, HT
;
Chen, C
;
資訊科學與工程研究所
It is known that the parallelism of non-uniform dependence loops is difficult to extract and is not effectively explored by the existing parallelization methods. In this paper, we propose new techniques to transform non-uniform dependence loops efficiently, based on their irregularity, by which more parallelism can be explored directly and effectively. Several effective mechanisms, including parallelization part splitting, partial parallelization decomposition, irregular loop interchange and growing pattern rt detection are created to exploit more parallelism degree for non-uniform loop structures. Compared with other existing methods, our new approach gives better performance. When the loop bounds is increased from 5 to 50, based on our evaluations, the speedup achieves 3.25 to 19.8 times better than that of the uniformization technique; and from 1.5 to 8.33 times better than that of the minimum dependence distance tiling technique. We evaluate our mechanisms in our simulation environment for various conditions and discuss the performance of them in this paper.
Enchanced linked-based cache coherence protocols with a hardware mechanism to reduce the migratory sharing overhead
(2000-12-01)
Pean, DL
;
Chen, C
;
資訊工程學系
;
Department of Computer Science
The linked-based cache coherence protocols, such as the IEEE Scalable Coherence Interface (SCI), have been widely implemented in current highly Scalable multiprocessor systems. Thus, we propose several enhanced linked-based cache coherence protocols in multiprocessor systems to evaluate their performance. However, migratory sharing data references in the linked-based systems still incur many cache misses that can be reduced by merging the invalidation/update requests and the cache misses. Research has been devoted to optimizing the migratory sharing references for the centralized directory coherence protocols, but their mechanisms cannot support the linked-based cache coherence protocols. This paper presents enhanced SCI protocols with an effective hardware technique to reduce the overhead of migratory sharing references for the linked-based cache coherence protocols. It reduces cost by eliminating some of the unnecessary supporting mechanisms in centralized directory protocols. The simulation results in SPLASH benchmarks show that our hardware methods enhanced the system performance by up to an average of 10%, by reducing the overhead of the migratory sharing references. The extra benefit of our mechanism is the elimination of the false sharing overhead by degrading a block to shared mode again.
Look-ahead memory consistency model
(1998)
Wu, CC
;
Pean, DL
;
Chen, C
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a hardware-centric lookahead memory consistency model that makes the data consistent according to the special ordering requirement of memory accesses for critical sections. The novel model imposes fewer restrictions an event ordering than previously proposed models thus offering the potential of higher performance. The architecture has the following features: (1) blocking and waking up processes by hardware, (2) allowing instructions to be executed our-of-order, (3) until having acquired the lock can the processor allow the requests for accessing the protected data to be evicted to the memory subsystem. The advantages of the look-ahead model include. (1) more program segments are allowed parallel execution (2) locks can be released earlier, resulting in reduced waiting times for acquiring lock, and (3) less network traffic because more write requests are merged by using two write caches.
ODCHP: a new effective mechanism to maximize parallelism of nested loops with non-uniform dependences
(2001-03-15)
Pean, DL
;
Chen, C
;
資訊工程學系
;
Department of Computer Science
There are many methods for nested loop partitioning. However, most of them perform poorly when partitioning loops with nonuniform dependences. This paper proposes a generalized and optimized loop partitioning mechanism to exploit parallelism from nested loops with non-uniform dependences. Our approach, based on dependence convex theory, will divide the loop into variable size partitions. Furthermore, the proposed algorithm partitions a nested loop by using the copy-renaming and the optimized partitioning techniques to minimize the number of parallel regions of the iteration space. Consequently, it outperforms the previous partitioning mechanisms of nested loops with non-uniform dependences. Many optimization techniques are used to reduce the complexity of the algorithm. Compared with other popular techniques, our scheme shows a dramatic improvement in the preliminary performance results. (C) 2001 Elsevier Science Inc. All rights reserved.