Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 113 papers for “hypercube multiprocessors”

Task migration in hypercube multiprocessors

Ming-Syan Chen⋆, Kang G. Shin · 1989

Allocation and deallocation of subcubes usually result in a fragmented hypercube where even if a sufficient number of hypercube nodes are available, they do not form a subcube large enough to execute an incoming task. As the fragmentation in conventional memory allocation can be handled by memory compaction, the fragmentation problem in a hypercube can be solved by task migration, i.e., relocating tasks within the hypercube to remove the fragmentation. The procedure for task migration closely depends on the subcube allocation strategy used, since active tasks must be relocated in such a way that the availability of subcubes can be detected by that allocation strategy.

Cited by 14Open access

Processor allocation in hypercube multiprocessors

S. Rai, Jerry L. Trahan, Thomas Smailus · IEEE Transactions on Parallel and Distributed Systems · 1995

The processor allocation problem requires recognizing and locating a free subcube that can accommodate a request for a subcube of a specified size for an incoming task. Methods reported in the literature fall into two strategies: bottom-up or bit mapped technique (BMT) and top-downer available cube technique (ACT). Our algorithm that solves the allocation problem in faulty hypercubes falls into the category of ACT's which offer the advantage over BMT's of quickly recognizing whether or not a requested subcube is available in the list of fault-free subcubes. We introduce new algebraic functions and the concept of separation factor to select a subcube for allocation. The notion of overlap-syndrome, defined in the text, quantifies the overlap among free subcubes. Our technique has full subcube recognition ability and thus recognizes more subcubes as compared to bit mapped techniques: Buddy, Gray code and its variants. The advantages of our approach over some of the existing ACT's in terms of fragmentation and overall completion time are described in the text and in simulation results.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 11

Cache coherent shared memory hypercube multiprocessors

Jiachen Ding, Laxmi N. Bhuyan · 2003

The authors examine the feasibility of building cache coherent shared memory multiprocessor systems on hypercube. Various shared memory schemes are investigated and compared with each other. The schemes considered are based on memory coherence algorithms for distributed shared memory and cache coherence protocols for other shared memory architectures. It is concluded that efficient cache coherent architectures can be built using hypercubes.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 6

Processor allocation in faulty hypercube multiprocessors

S. Rai, Jerry L. Trahan, Thomas Smailus · 1993 IEEE International Symposium on Circuits and Systems · 2002

The processor allocation problem in hypercubes is to recognize and locate a free subcube that can accommodate a request for a subcube of a specified size for an incoming task. A new approach for this processor allocation problem in faulty hypercubes is presented. A new concept is introduced, i.e., the growth factor, to select a subcube for allocation, which in turn utilizes the notion of overlap-syndrome to quantify the overlap among free subcubes. The authors' technique has full subcube recognition ability and thus recognizes more subcubes as compared to buddy, Gray code and its variants. The advantages of their approach over some existing approaches are described.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 0

A multicast algorithm for hypercube multiprocessors

Shih-hsien Sheu, Chang-biau Yang · 1992

Depending on different switching technologies, the multicast communication problem has been formulated as three different graph theoretical problems: the Steiner tree problem, the multicast tree problem, and the multicast path problem. Our efforts in this paper are to reduce the communication traffic of multicast in hypercube multiprocessors. We propose three heuristic algorithms for the three problem models. Our multicast path algorithm is distributed, our Steiner tree algorithm is centralized, and our multicast tree algorithm is hybrid. Compared with the previous results by simulation, each of our heuristic algorithms improves the communication traffic in the corresponding multicast problem model. 2001 Academic Press Key Words: hypercube; multicast; NP-complete; heuristic algorithm. 1.

Cited by 0

High performance communications for hypercube multiprocessors

Gregory D. Buzzard · Deep Blue (University of Michigan) · 1988

A large potential exists for increasing the communication performance of hypercube multiprocessors. The development of this potential will allow an increasing variety of algorithms to be efficiently executed on these systems. In this dissertation we introduce a classification scheme for parallel programs and their communications. The classification scheme establishes a framework to facilitate discussion of communication system issues. This framework is then used to identify classes of programs with similar communication characteristics. The exploration of communication issues is divided into two broad groups: communications among neighboring nodes or broadcasts to all other nodes, and communications among non-neighboring nodes. We show that the execution time of many programs that employ communications from the first group may be improved considerably by utilizing a new operating system communication module that we have developed and implemented. We then describe the minor architectural support that is necessary to allow the remainder of the programs that use broadcast or neighboring communications to take advantage of our improved communication system. Finally, we develop a new routing scheme that reduces the communication latency for communications among non-neighboring nodes. As a proof of principle, we provide a detailed description of a communication architecture that employs this routing scheme and also allows greater overlap of computations with communications. Our simulations of this new architecture predict significant performance improvements for non-neighboring communications as well as further improvements to neighboring and broadcast communications.

Cited by 5

Large-grain pipelining on hypercube multiprocessors

Chung‐Ta King, Lionel M. Ni · University of North Texas Digital Library (University of North Texas) · 1988

A new paradigm, called large-grain pipelining, for developing efficient parallel algorithms on distributed-memory multiprocessors, e.g., hypercube machines, is introduced. Large-grain pipelining attempts to maximize the degree of overlapping and minimize the effect of communication overhead in a multiprocessor system through macro-pipelining between the nodes. Algorithms developed through large-grain pipelining to perform matrix multiplication are presented. To model the pipelined computations, an analytic model is introduced, which takes into account both underlying architecture and algorithm behavior. Through the analytical model, important design parameters, such as data partition sizes, can be determined. Experiments were conducted on a 64-node NCUBE multiprocessor. The measured results match closely with the analyzed results, which establishes the analytic model as an integral part of algorithm design. Comparison with an algorithm which does not use large-grain pipelining also shows that large-grain pipelining is an efficient scheme for achieving a greater parallelism. 14 refs., 12 figs.

Cited by 0Open access

Load Balanced Sort on Hypercube Multiprocessors

B. Abah, F. Özgüner, Abdulla Bataineh · 2005

A parallel algorithm for sorting n elements evenly distributed over 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sup> = p nodes of a d-dimensional hypercube is given. The algorithm ensures that the nodes always receive equal number of elements (n/p) at the end, regardless of the skew in data distribution.

Cited by 7

Parallel Algorithm Design Considerations for Hypercube Multiprocessors

Ni, Lionel Ming-Shuan, King, C.T., Prins, P. · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 1987

The design of efficient parallel algorithms in a message-based, distributed-memory multiprocessor system should consider both time-space tradeoffs and computation-communication tradeoffs. A generic model of distributed hypercube multiprocessors is introduced to characterize those important parameters that would affect the performance of algorithms. To implement a good data-parallel algorithm on the hypercube multiprocessor, one has to consider the number of processors required, an efficient way to partition the data, and an efficient way to map partitions into processors. Two simple examples, array summation and matrix multiplication, are used to demonstrate various techniques to solve these problems. An analysis based on the proposed model is presented.

Cited by 10

PARALLEL MATRIX MULTIPLICATION ALGORITHMS ON HYPERCUBE MULTIPROCESSORS

PeiZong Lee · International Journal of High Speed Computing · 1995

In this paper, we present three parallel algorithms for matrix multiplication. The first one, which employs pipelining techniques on a mesh grid, uses only one copy of data matrices. The second one uses multiple copies of data matrices also on a mesh grid. Although data communication operations of the second algorithm are reduced, the requirement of local data memory for each processing element increases. The third one, which uses a cubic grid, shows the trade-offs between reducing the computation time and reducing the communication overhead. Performance models and feasibilities of these three algorithms are studied. We analyze the interplay among the numbers of processing elements, the communication overhead, and the requirements of local memory in each processing element. We also present experimental results of these three algorithms on a 32-node nCUBE-2 computer.

Cited by 3

Scheduling independent tasks on partitionable hypercube multiprocessors

Bhagirath Narahari, Ramesh Krishnamurti · 2002

A partitionable hypercube allows simultaneous execution of multiple tasks, where each task can be executed on a choice of subcubes. This paper considers the problem of static nonpreemptive scheduling of w independent tasks on a n processor partitionable hypercube system to minimize the overall finishing time of the w tasks. Each task can be executed on subcubes of different sizes, with smaller execution times on larger subcubes. A schedule determines the size of the subcube to be assigned to each task and schedules these tasks on the processors in the hypercube system. The problem of finding the optimal schedule, with minimum finishing time, is known to be NP-hard. This paper presents a fast polynomial time approximation algorithm for the problem, and derives a tight worst-case performance bound of 2 for the algorithm.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 7

Relay approach message routing in hypercube multiprocessors

Yu-Xiang Lan, Abdol‐Hossein Esfahanian, Lionel M. Ni · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1988

A relay approach message routing for hypercube multiprocessors is proposed which is able to forward a received message immediately after the address fields of the message are received if the outgoing channels are not blocked. The relay message routing can significantly reduce the communication latency compared with the store-and-forward message routing. Based on the relay approach, a distributed routing mechanism which is able to handle unicast, multicast, and broadcast interprocessor communications is proposed. These three types of interprocessor communication are modeled as an Optimal Multicast Tree problem which can guarantee a minimum message delivery time. Network traffic is minimized for the cases of unicast and broadcast and close to minimum for the case of multicast. A hardware router design based on the proposed distributed relay routing is discussed.

Cited by 8

Graceful Degradation on Hypercube Multiprocessors Using Data Redistribution

Chung‐Chi Jim Li, W.K. Fuchs · 2005

A data redistribution approach to graceful degradation is described in this paper for hypercube multiprocessors. CPU-bound hypercube programs using the described second-order parametrized data distribution technique can run on a group of cubes of any size to achieve graceful degradation without recompila tion. A transmission mechanism has been designed to switch the performance of a second-order parametrized data distribution hypercube program to that of a corresponding first-order program when the latter is superior. A package of procedures has been implemented on the Intel iPSC/2 hypercube to support the approach.

Cited by 9

ADAPTIVE ROUTING FOR HYPERCUBE MULTIPROCESSORS: A PERFORMANCE STUDY

Douglas S. Reeves, Edward F. Gehringer · International Journal of High Speed Computing · 1994

Through simulation, we studied the performance of three adaptive “wormhole” routing strategies, and compared them with static routing. Since adaptive routing is susceptible to deadlock, an abort-and-retry strategy was used to prevent it from arising. The impact of packetization of long messages and buffering at message destinations were also studied. Results are presented and analyzed for a variety of hardware configurations and traffic conditions. The combination of adaptive routing, abort-and-retry, and buffering at the destination is shown to achieve excellent performance for modest cost.

Cited by 5

Parallel branch and bound algorithms on hypercube multiprocessors

Tarek S. Abdelrahman, Trevor Mudge · 1988

Branch and Bound (BB) algorithms are a generalization of many search algorithms used in Artificial Intelligence and Operations Research. This paper presents our work on implementing BB algorithms on hypercube multiprocessors. The 0-1 integer linear programming (ILP) problem is taken as an example because it can be implemented to capture the essence of BB search algorithms without too many distracting problem specific details. A BB algorithm for the 0-1 ILP problem is discussed. Two parallel implementations of the algorithm on hypercube multiprocessors are presented. The two implementations demonstrate some of the tradeoffs involved in implementing these algorithms on multiprocessors with no shared memory, such as hypercubes. Experimental results from the NCUBE/six show the performance of the two implementations of the algorithm. Future research work is discussed.

Cited by 19Open access