International Journal of High Speed Computing

Tiling is a technique for extraction of parallelism which groups iterations of a nest of "for" loops into blocks called tiles which can be scheduled for execution on the workstations connected by a network. Extraction of parallelism will be maximum when the workstations are busy in computation most of the time. Hence idle time of tiling is a very important parameter. In this paper we have presented results on the study of tiling transformation with respect to computation time and idle time. In our study we have considered tiles of rectangular shape and of size n₁×n₂. The iteration space can, however, be rectangular or parallelogram shaped and of size N₁×N₂. The results presented in this paper can be used for tiling of iteration spaces such that idle time is minimum and can be easily integrated in a parallelising compiler. Modelling communication between workstations is important for tiling transformation. We have developed a new improved model for modelling communication between workstations.

In this paper, we present an adaptive fault-tolerant wormhole routing algorithm for hypercubes by using 4 virtual networks. Each node is identified to be in one of the four states: safe, ordinarily unsafe, strongly unsafe, and faulty. Based on the concept of unsafe nodes, we design a routing algorithm for hypercubes that can tolerate at least n-1 faulty nodes and can route a message via a path of length no more than the Hamming distance between the source and destination plus four. Previous algorithms which achieve the same fault tolerant ability need at least 5 virtual channels per physical channel. Simulation results show that our algorithm outperforms previous known results.

In software Distributed Shared Memory (SDSM) systems, the large coherence granularity imposed by virtual memory page size tends to induce false sharing, which may lead to heavy network traffic or useless page misses on barrier operations.

In this paper, we propose a method to alleviate the coherence overhead of barrier synchronization in the SDSM systems. It performs static analysis on a shared-memory program to examine data dependency between processors across global barriers, and then special primitives are inserted into the program in order to exploit the dependency information at run time. If the data modified before a barrier will be accessed by some of the other processors after the barrier, coherence messages are transferred only to the processors through the inserted primitives. Furthermore, if the modified data will not be used by any other processors, the primitives enforce the coherence messages to be delivered only to master process after the parallel execution of the program completes.

We implemented the static analysis with SUIF parallelizing compiler and then evaluated the execution performance of modified programs in a 16-node SDSM system supporting AURC protocol. The experimental results show that our method is very effective at reducing the useless coherence messages, and also can improve the execution time substantially by reducing false sharing misses.

We consider the problem of finding Hamiltonian cycles, linear arrays and rings of a faulty supercube, if any. The proof of the existence of Hamiltonian cycles in hypercubes is easy due to the fact they are symmetric graphs. Since the supercube is asymmetric, the proof of the existence of Hamiltonian cycles is not trivial. We show that for any supercube S_N, where N is the number of nodes in the supercube, there exists a Hamiltonian cycle. This implies that for any r such that 3≤r≤N, there exists a cycle of r nodes in a supercube. There are embedding algorithms proposed in this paper. The embedding algorithms show a ring with any number of nodes which can be embedded in a faulty supercube with load 1, congestion 1 and dilation 4 such that O(n²-(⌊log₂ m⌋)²) faults can be tolerated, where n is the dimension of the supercube and m is the number of nodes of the ring.