Research Proposal Extension INTENS- Interconnection Network Simulations
- 格式：pdf
- 大小：135.61 KB
- 文档页数：6
Research Proposal Extension INTENS - Interconnection Network Simulations October 12, 1998
Miltos Grammatikakis Parallel Systems, Faculty of Informatics University of Oldenburg D-261roduction
We request renewal of access to KFA-Julich parallel computing facilities, and in particular the Cray-T3E systems, in order to develop further our research on parallel system interconnects. Our past activities and future work within our project's areas: (a) parallel simulation of ATM routers and networks, and (b) communication and consistency benchmarks of the Cray-T3E system architecture are brie y described below.
2.1 Past activities (ATM): July 1997 - October 1998
Sorting Based Approach
During this time, we implemented an algorithm for parallel simulation of packet-switched interconnection networks using C & MPI on the Cray-T3E. The algorithm was based on sorting integer con ict-function values and the simulation granularity was at the packet-level. An optimized version of this algorithm avoids relocating packet information by using a global packet indexing scheme and e cient bit-vector operations. As a benchmark we considered a symmetric hypercube interconnection network. Our optimized version can process 500K packet moves in just 1 sec on a Cray-T3E with 32 PEs and achieves 60% parallel e ciency; for more information on the algorithm and our MPI implementation on the Cray-T3E (and comparisons with Cray-T3D and CM5) refer to 6, 7]. We have recently implemented multicast packets with limited message copying by using spanning-trees. Multicast addresses are incorporated in the packet description using linked lists and dynamic memory allocation. In our current implementation, multicasting packets headed to di erent switch ports may depart the switch at di erent times. The con ictfunction scheme has also been extended to accommodate multicasting.
Priority Queue Based Approach
1
An alternative to sorting for network simulation is the use of priority queues, supporting parallel priority insert and deletemin operations 12]. We have implemented distributed splay trees using MPI 18], and concurrent priority heaps using shared-memory (ShMem) locks per data 20, 11]. In addition, we have designed and implemented a new concurrent data structure called virtual shared-memory priority queue (BCPQ). The rst implementation uses MPI to implement a distributed priority queue data structure. A special root PE provides the global view of a heap, with each node consisting of a splay tree of local items. Insertions and deletions invoke always the root PE. The second implementation uses a normal heap data structure with data at each node stored in arrays at predetermined randomly hashed PE locations. The third implementation is based on distributed circular lists and uses shared-memory (ShMem) locks per processor. For item insertion, the BCPQ data structure exploits binary search procedures both for locating the PE, and also for nding the position within the circular list where the item is to be inserted. The deletemin function (and deletemax if necessary) can also be implemented e ciently. An interesting load balancing scheme based on pre x computations preserves the relative order of elements and helps in avoiding workload imbalance. The scheme provides dynamic work allocation and e cient use of the parallel computing resources. Automatic as well as user control of the load balancing process is provided. We have also considered algorithms for implementing mutual exclusion on the Cray-T3E virtual shared-memory using various atomic operations 19]. Our implementations compared to the Cray shmem lock library functions achieve time performance improvements of above three orders of magnitude for a 64-processor T3E-900 (see attached reference 4]). Our results hold for either small or large critical sections, and make the possibility of implementing e ciently concurrent data structures on the Cray-T3E virtual shared-memory a viable one. More recently we have focused on the optimization and experimental analysis of distributed (MPI library based) and concurrent (Cray ShMem library based) implementations of priority queue data structures. The optimizations for BCPQ included algorithmic, and runtime optimizations. A local findPE routine was used for nding the target list, thus avoiding locking target lists. The new findPE implementation is based on broadcasting maximum priorities of all local lists to all PEs. This all-to-all broadcast is coded using shmem int p and shmem quiet, which is more efcient than using the Cray MPP shmem int bcast routine. Other algorithmic optimizations have been directed at shared memory locks with improvements over the Cray shmem lock library functions at above three orders of magnitude on a 64-processor T3E-900 4]. Finally, the optimized version implements the PEm computation using node-to-neighbor communication (textttshmem int p) and parallel searching of the distributed nonempty eld patterns. For example, a distributed nonempty eld of 1; 1; 1; 1; 1; 0; 0; 0 implies PEm= 4, since PE4 is the last nonempty PE; notice that the distributed list is compact, i.e., all local lists to the right of an empty local list are empty. Both a Cray library eureka - or shmem event -based parallel searching approach, and a direct shmem int sum to all based implementation were slower alternatives for the PEm computation. By considering these priority queues in a switch simulation environment with continuous tra c assumptions, we have found that both concurrent implementations have comparable performance and outperform the distributed ones 8] 1. They also o er additional modularity and can form a parallel library which can be used for further research in network simulation. The library has been optimized for Cray-T3E systems; for example, to support a high degree of data concurrency very fast virtual shared memory binary locking mechanisms have already been implemented. Although, there is already upward compatibility of ShMem routines on new Cray systems, it is expected that MPI-2 will open new horizons for extensions of this work. While the data access layer will have to be rewritten, most of the main part of the code can remain unchanged.
Miltos Grammatikakis Parallel Systems, Faculty of Informatics University of Oldenburg D-261roduction
We request renewal of access to KFA-Julich parallel computing facilities, and in particular the Cray-T3E systems, in order to develop further our research on parallel system interconnects. Our past activities and future work within our project's areas: (a) parallel simulation of ATM routers and networks, and (b) communication and consistency benchmarks of the Cray-T3E system architecture are brie y described below.
2.1 Past activities (ATM): July 1997 - October 1998
Sorting Based Approach
During this time, we implemented an algorithm for parallel simulation of packet-switched interconnection networks using C & MPI on the Cray-T3E. The algorithm was based on sorting integer con ict-function values and the simulation granularity was at the packet-level. An optimized version of this algorithm avoids relocating packet information by using a global packet indexing scheme and e cient bit-vector operations. As a benchmark we considered a symmetric hypercube interconnection network. Our optimized version can process 500K packet moves in just 1 sec on a Cray-T3E with 32 PEs and achieves 60% parallel e ciency; for more information on the algorithm and our MPI implementation on the Cray-T3E (and comparisons with Cray-T3D and CM5) refer to 6, 7]. We have recently implemented multicast packets with limited message copying by using spanning-trees. Multicast addresses are incorporated in the packet description using linked lists and dynamic memory allocation. In our current implementation, multicasting packets headed to di erent switch ports may depart the switch at di erent times. The con ictfunction scheme has also been extended to accommodate multicasting.
Priority Queue Based Approach
1
An alternative to sorting for network simulation is the use of priority queues, supporting parallel priority insert and deletemin operations 12]. We have implemented distributed splay trees using MPI 18], and concurrent priority heaps using shared-memory (ShMem) locks per data 20, 11]. In addition, we have designed and implemented a new concurrent data structure called virtual shared-memory priority queue (BCPQ). The rst implementation uses MPI to implement a distributed priority queue data structure. A special root PE provides the global view of a heap, with each node consisting of a splay tree of local items. Insertions and deletions invoke always the root PE. The second implementation uses a normal heap data structure with data at each node stored in arrays at predetermined randomly hashed PE locations. The third implementation is based on distributed circular lists and uses shared-memory (ShMem) locks per processor. For item insertion, the BCPQ data structure exploits binary search procedures both for locating the PE, and also for nding the position within the circular list where the item is to be inserted. The deletemin function (and deletemax if necessary) can also be implemented e ciently. An interesting load balancing scheme based on pre x computations preserves the relative order of elements and helps in avoiding workload imbalance. The scheme provides dynamic work allocation and e cient use of the parallel computing resources. Automatic as well as user control of the load balancing process is provided. We have also considered algorithms for implementing mutual exclusion on the Cray-T3E virtual shared-memory using various atomic operations 19]. Our implementations compared to the Cray shmem lock library functions achieve time performance improvements of above three orders of magnitude for a 64-processor T3E-900 (see attached reference 4]). Our results hold for either small or large critical sections, and make the possibility of implementing e ciently concurrent data structures on the Cray-T3E virtual shared-memory a viable one. More recently we have focused on the optimization and experimental analysis of distributed (MPI library based) and concurrent (Cray ShMem library based) implementations of priority queue data structures. The optimizations for BCPQ included algorithmic, and runtime optimizations. A local findPE routine was used for nding the target list, thus avoiding locking target lists. The new findPE implementation is based on broadcasting maximum priorities of all local lists to all PEs. This all-to-all broadcast is coded using shmem int p and shmem quiet, which is more efcient than using the Cray MPP shmem int bcast routine. Other algorithmic optimizations have been directed at shared memory locks with improvements over the Cray shmem lock library functions at above three orders of magnitude on a 64-processor T3E-900 4]. Finally, the optimized version implements the PEm computation using node-to-neighbor communication (textttshmem int p) and parallel searching of the distributed nonempty eld patterns. For example, a distributed nonempty eld of 1; 1; 1; 1; 1; 0; 0; 0 implies PEm= 4, since PE4 is the last nonempty PE; notice that the distributed list is compact, i.e., all local lists to the right of an empty local list are empty. Both a Cray library eureka - or shmem event -based parallel searching approach, and a direct shmem int sum to all based implementation were slower alternatives for the PEm computation. By considering these priority queues in a switch simulation environment with continuous tra c assumptions, we have found that both concurrent implementations have comparable performance and outperform the distributed ones 8] 1. They also o er additional modularity and can form a parallel library which can be used for further research in network simulation. The library has been optimized for Cray-T3E systems; for example, to support a high degree of data concurrency very fast virtual shared memory binary locking mechanisms have already been implemented. Although, there is already upward compatibility of ShMem routines on new Cray systems, it is expected that MPI-2 will open new horizons for extensions of this work. While the data access layer will have to be rewritten, most of the main part of the code can remain unchanged.
