International Journal of Foundations of Computer Science

This paper briefly reviews some of the more popular parallel-computer models-pipelined optical bus, optical transpose interconnect system (OTIS), and partitioned optical passive stars (POPS) network-that employ optical interconnect. The interconnect topology and some simple algorithms for each model are also described.

Gang scheduling has been widely used as a practical solution to the dynamic parallel job scheduling problem. To overcome some of the limitations of traditional Gang scheduling algorithms, Concurrent Gang is proposed as a class of scheduling policies which allows the flexible and simultaneous scheduling of multiple parallel jobs. It hence improves the space sharing characteristics of Gang scheduling while preserving all other advantages. To provide a sound analysis of Concurrent Gang performance, a novel methodology based on the traditional concept of competitive ratio is also introduced. Dubbed dynamic competitive ratio, the new method is used to compare dynamic bin packing algorithms used in this paper. These packing algorithms apply to the Concurrent Gang scheduling of a workload generated by a statistical model. Moreover, dynamic competitive ratio is the figure of merit used to evaluate and compare packing strategies for job scheduling under multiple constraints. It will be shown that for the unidimensional case there is a small difference between the performance of best fit and first fit; first fit can hence be used without significant system degradation. For the multidimensional case, when memory is also considered, we concluded that the packing algorithm must try to balance the resource utilization in all dimensions simulataneously, instead of given priority to only one dimension of the problem.

In this paper, we report a performance gap betweeen a schedule with small makespan on the task scheduling model and the corresponding parallel program on distributed memory parallel machines. The main reason of the gap is the software overhead in the interprocessor communication. Therefore, speedup ratios of schedules on the model do not approximate well to those of parallel programs on the machines. The purpose of the paper is to get a task scheduling algorithm that generates a schedule with good approximation to the corresponding parallel program and with small makespan.

For this purpose, we propose algorithm BCSH that generates only bulk synchronous schedules. In those schedules, no-communication phases and communication phases appear alternately. All interprocessor communications are done only in the latter phases, and thus the corresponding parallel programs can make better use of the message packaging technique easily. It reduces many software overheads of messages form a source processor to the same destination processor to almost one software overhead, and improves the performance of a parallel program significantly.

Finally, we show some experimental results of performance gaps on BCSH, Kruatrachue's algorithm DSH, and Ahmad et al's algorithm ECPFD. The schedules by DSH and ECPFD are famous for their small makespans, but message packaging can not be effectively applied to the corresponding program. The results show that a bulk synchronous schedule with small makespan has advantages that the gap is small and the corresponding program is a high performance parallel one.

Load balancing is a critical issue for achieving good performance in parallel and distributed systems. However, this issue is neglected in the research area of software DSMs in the past decade. Based on the observation that scientific applications can be classified into two categories: iterative and non-iterative, we propose two dynamic scheduling schemes for these two cases respectively in this paper. For iterative scientific applications, a dynamic task migration technique is proposed which characterizes itself with integrating computation migration and data migration together. An affinity-based self scheduling (ABS) is proposed for non-iterative scientific applications, which take both the static and dynamic processor affinity into consideration when scheduling. The target experiment platform is a state-of-the-art home-based DSM system named JIAJIA. Performance evaluation results show that the novel task migration scheme improves the performance ranging from 36% to 50% compared with a static task allocation scheme in a metacomputing environment, and performs better than traditional task (computation-only) migration approach about 12.5% for MAT, and 37.5% for SOR and EM3D. Higher resource utilization is achieved via the new task migration scheme too. In comparison with other loop scheduling schemes, the ABS achieves the best performance among all scheduling schemes in a metacomputing environment because of the reduction of synchronization overhead and the great improvement of waiting time resulting from load imbalance.

The present super computer will be replaced by a massively parallel computer consisting of a large number of processing elements which satisfy the continuous increasing depend for computing power. Practical parallel computing model has been expected to develop efficient parallel algorithms on massively parallel computers. Thus, we have presented a practical parallel computation model LogPQ by taking account of communication queues into the LogP model. This paper addresses the performance of a parallel matrix multiplication algorithm using LogPQ and LogP models. The parallel algorithm is implemented on Cray T3E and the parallel performances are compared with on the old machine CM-5. This shows that the communication network of T3E has superior buffering behavior than CM-5, in which we don't need to prepare extra buffering on T3E. Although, a little effect remains for both of the send and receive bufferings. On the other hand, the effect of message size remains, which shows the necessity of the overhead and gap proportional to the message size.

Prediction is a critical component in the achievement of application execution performance. The development of adequate and accurate prediction models is especially difficult in local-area clustered environments where resources are distributed and performance varies due to the presence of other users in the system. This paper discusses the use of stochastic values to parameterize cluster application performance models. Stochastic values represent a range of likely behavior and can be used effectively as model parameters. We describe two representations for stochastic model parameters and demonstrate their effectiveness in predicting the behavior of several applications under different workloads on a contended network of workstations.

We propose a novel approach for shortest path routing in wireless mobile networks. The approach makes use of n mobile agents initially launched from n mobile nodes forming the network. The agents move randomly from node to node and update routing information as they go. The approach is presented in this paper with two protocols. Both of them exhibit good performance in terms of the network and computing resource consumptions. The first protocol relies on independent mobile agents and imposes a minimum bandwidth requirement on individual mobile agents. Each agent carries the link state of its creator and this information remains unchanged except when the mobile agent returns to the home node. The second protocol is a refinement of the first protocol, with some form of interaction between the mobile agents. Each agent maintains the routing table of its creator instead of link state. The randomly walking agents spread the update information and compute the shortest paths via exchanging network state information between the routing tables they carry and the routing tables at the nodes they traverse. The correctness of the protocols is proven. Our analysis shows that the agent cooperation improves the system performance when dealing with topology and link cost changes.

A term calculus corresponding to pure prolog is introduced and extended by an if-then-else construct to obtain the expressiveness of pure prolog + cut. In contrast to functional terms which have a single value the evaluation of predicational terms leads to an enumeration of the several (finite or infinite) solutions. A user can control up to which point this stream of answers is computed and restrict his attention to a special position in this stream. We show that this can not be achieved inside the program. The addition of if-then-else offers the possibility to pick the first answer but this does not carry over to the second or later position. This is proved used the denotational semantics of the predicational language.

This paper first shows that

(1) the class of languages recognized by o(log n) space-bounded two-way Monte Carlo Turing machines is not closed under concatenation, Kleene closure, and length-preserving homomorphism, and

(2) the class of languages recognized by o(log log n) space-bounded two-way unbounded error probabilistic Turing machines is not closed under each of the above operations.

We then show that the class of languages accepted by S(n) space-bounded two-way alternating Turing machines is not closed under each of the above operations for log log n ≤ S(n) ≤ o(log n).