A lock mechanism is essential for synchronization on the multiprocessor systems. The conventional queuing lock has two bus traffics that are the initial and retry of the lock-read. This paper proposes the new locking protocol, called WPV (waiting processor variable) lock mechanism, which has only one lock-read bus traffic command. The WPV mechanism accesses the shared data in the initial lock-read phase that is held in the pipelined protocol until the shared data is transferred. The WPV mechanism also uses the cache state lock mechanism to reduce the locking overhead and guarantees the FIFO lock operations in the multiple lock contentions. In this paper, we also derive the analytical model of WPV lock mechanism as well as conventional memory and cache queuing lock mechanisms. The simulation results on the WPV lock mechanism show that about 50% of access time is reduced comparing with the conventional queuing lock mechanism.

This paper presents a cost error measurement scheme and relaxed synchronization method, for simulated annealing on a distributed memory multicomputer, which predicts the amount of cost error that an algorithm will tolerate. An adaptive error control method is developed and implemented on an Intel iPSC/2.>

Simulated annealing is a powerful and general algorithm for solving combinatorial optimization problems, but it takes an extremely long time to execute. The resulting cost error from a reduction of the costly synchronization in distributed-memory multicomputers is tolerated by the hill climbing nature of simulated annealing. The authors address the behavior of algorithms that contain the cost error. The new cost error measurement and relaxing synchronization method predicts the amount of cost error that an algorithm will tolerate and still converge. This method also explains certain interesting phenomena of the cost error statistically. Finally, the authors apply the new method to the problem of composite material stock cutting. Implementation results of the parallel space-decomposition algorithm on an Intel iPSC/2 are reported.

A new algorithm, the ID algorithm, is presented which minimizes the fault-detection latency. In the ID algorithm, a fault is detected as soon as the fault occurs instead of at problem termination. For n/sup 2/ processors, the fault-latency time of the ID algorithm is 1/n of that of the checksum algorithm with a run-time penalty of O(n log/sub 2/ n) in an n*n matrix operation. This algorithm has better performance in terms of error coverage and expected run time in large-scale matrix multiplications such as signal and image processing, weather prediction, and finite-element analysis.>