International Journal of High Speed Computing

Binary search trees with costs α and β on the left and right edges (lopsided binary search trees) are important in the construction of optimum prefix codes. In this paper we derive lower bounds for the external pathlengths of lopsided binary trees. It is found that the lower bound is tight if the cost difference (the difference in maximum cost and the minimum cost) is small but quite sharp when the cost difference is large. We suggest alternative ways to construct the lopsided binary tree when the cost difference is high to improve the lower bound.

This paper introduces an optically interconnected distributed shared memory system. The distributed shared memory approach integrates both shared memory and distributed memory system ideas to extract the strengths of each while balancing their respective weaknesses. The system is a system based on a photonic network to support the high communication requirement of . The employs wavelength division multiple access on the photonic network, enabling multiple channels to be formed on a single optical fiber. A result of the high communication capacity is the simplification of the global address mapping problem. This simplified uniform address allocation scheme is introduced. The advantages of the proposed approach are examined through a performance analysis based on a closed queueing network which has been validated through extensive simulation. The performance of the system is evaluated in terms of transaction time of a memory request and system throughput. The impact of variations in the number of channels and processors in the system on these metrics is studied. The effect of variations in memory and channel service times are also evaluated.

The ability of the existence of vectorizing compilers to extract vector instructions from blocks of sequential code does not remove the need for proper choice of software algorithms. In this paper, we study the vectorization of the insertion sorting, shellsort, and radix sortings. To measure their suitability for vectorization, we have implemented them on a Convex C-l, and computed the scalar/vector speedup for each method. We observed that for sorting methods based on compare/exchange, contingent methods often thought unsuitable for vectorization, the insertion sort is well performed, especially when using an M-section approach. And for radix sortings, the LSD methods are more suited to vectorization compared to the MSD methods. Finally, based on our study and experiments, we suggest that the straight radix sorting is a good choice for use on vector supercomputers.

This paper discusses an experiment with a dataflow execution model for logic programs implemented on the transputer. The execution model is supported by a dataflow virtual machine, on which the execution mechanism for AND/OR-parallelism is developed. The real-time evaluation shows that small scale parallelism can be exploited from the dataflow graphs compiled from the logic programs. A conventional dataflow architecture supporting the implemented model has been emulated on a multitransputer system.