Unicast-based multicast communication in wormhole-routed networks

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log ₂ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given     

On loop transformations for generalized cycle shrinking

This paper describes several loop transformation techniques for extracting parallelism from nested loop structures. Nested loops can then be scheduled to run in parallel so that execution time is minimized. One technique is called selective cycle shrinking, and the other is called true dependence cycle shrinking. It is shown how selective shrinking is related to linear scheduling of nested loops and how true dependence shrinking is related to conflict-free mappings of higher dimensional algorithms into lower dimensional processor arrays. Methods are proposed in this paper to find the selective and true dependence shrinkings with minimum total execution time by applying the techniques of finding optimal linear schedules and optimal and conflict-free mappings proposed by W. Shang and A.B. Fortes     

The fault-tolerant extension problem for complete multipartitenetworks

We develop a characterization for m-fault-tolerant extensions, and for optimal m-fault-tolerant extensions, of a complete multipartite graph. Our formulation shows that this problem is equivalent to an interesting combinatorial problem on the partitioning of integers. This characterization leads to a new procedure for constructing an optimal m-fault-tolerant extension of any complete multipartite graph, for any m⩾0. The proposed procedure is mainly useful when the size of the graph is relatively small, because the search time required is exponential. This exponential search, however, is not always necessary. We prove several necessary conditions that help us, in several cases, to identify some optimal m-fault-tolerant extensions without performing any search     

Allocating tree structured programs in a distributed system withuniform communication costs

Studies the complexity of the problem of allocating m modules to n processors in a distributed system to minimize total communication and execution costs. When the communication graph is a tree, Bokhari has shown that the optimum allocation can be determined in O(mn²) time. Recently, this result has been generalized by Fernandez-Baca, who has proposed an allocation algorithm in O(mn^k+1) when the communication graph is a partial k-tree. The author shows that in the case where communication costs are uniform, the module allocation problem can be solved in O(mn) time if the communication graph is a tree. This algorithm is asymptotically optimum     

Scheduling DAG's for asynchronous multiprocessor execution

A new approach is given for scheduling a sequential instruction stream for execution “in parallel” on asynchronous multiprocessors. The key idea in our approach is to exploit the fine grained parallelism present in the instruction stream. In this context, schedules are constructed by a careful balancing of execution and communication costs at the level of individual instructions, and their data dependencies. Three methods are used to evaluate our approach. First, several existing methods are extended to the fine grained situation. Our approach is then compared to these methods using both static schedule length analyses, and simulated executions of the scheduled code. In each instance, our method is found to provide significantly shorter schedules. Second, by varying parameters such as the speed of the instruction set, and the speed/parallelism in the interconnection structure, simulation techniques are used to examine the effects of various architectural considerations on the executions of the schedules. These results show that our approach provides significant speedups in a wide-range of situations. Third, schedules produced by our approach are executed on a two-processor Data General shared memory multiprocessor system. These experiments show that there is a strong correlation between our simulation results, and these actual executions, and thereby serve to validate the simulation studies. Together, our results establish that fine grained parallelism can be exploited in a substantial manner when scheduling a sequential instruction stream for execution “in parallel” on asynchronous multiprocessors     

Pipelining and bypassing in a VLIW processor

This short note describes issues involved in the bypassing mechanism for a very long instruction word (VLIW) processor and its relation to the pipeline structure of the processor. The authors first describe the pipeline structure of their processor and analyze its performance and compare it to typical RISC-style pipeline structures given the context of a processor with multiple functional units. Next they study the performance effects of various bypassing schemes in terms of their effectiveness in resolving pipeline data hazards and their effect on the processor cycle time     

A delta transform approach to loop gain-phase shaping design of robust digital control systems

This paper addresses the existence of loop gain-phase shaping (LGPS) solutions for the design of robust digital control systems for SISO, minimum-phase, continuous-time processes with parametric uncertainty. We develop the frequency response properties of LGPS for discrete-time systems using the Δ-transform, a transform method that applies to both continuous-time and discrete-time systems. A theorem is presented which demonstrates that for reasonable specifications there always exists a sampling period such that the robust digital control problem has a solution. Finally, we offer a procedure for estimating the maximum feasible sampling period for LGPS solutions to robust digital control problems.     

MEETING THE IT CHALLENGES OF BUSINESS The Changing Mandate for MBAs

What is the implication for business when information technology (IT) changes in the workplace without a commensurate change in the composition of business programs educating tomorrow's employees? A survey of MBA graduates forms the basis of this article on the IT skills needed in the marketplace.     

Base-type languages: Program design by upper semantic approximation

Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 140–155, July–August 1994.