Search

Embedding deals with simulating one architecture called guest into another called host, as it helps in modifying algorithms designed for the guest graph to be implemented in the host graph. In this paper, we have obtained the optimal wirelength of embedding (K 9 - C 9) n into P 9 n and certain trees, where (K 9 - C 9) n is the Cartesian product of complete graph on 9 vertices with a deletion of a cycle on 9 vertices and P 9 n is a path on 9 n vertices. Furthermore, we have also obtained the wirelength of embedding the Cartesian product graph (K 9 - C 9) n into Banana trees and Firecracker trees. [ABSTRACT FROM AUTHOR]

Embedding an interconnection network into another network is one of the important problems in parallel processing. In this paper, we study embedding of linear arrays (paths) of maximum length in O-shaped meshes (O-shaped grid graphs). This is equal to finding a longest path in an O-shaped mesh (grid graph). An O-shaped mesh is a 2D mesh that a smaller 2D mesh is removed from it. The removed nodes can be considered as faulty processor. We give a linear-time parallel algorithm for this problem. To show the algorithm finds an optimal path, first we prove some upper bounds on the length of the longest paths, then we show that how our algorithm meets these upper bounds. [ABSTRACT FROM AUTHOR]

Graph embedding is an important technology in simulating parallel structures and designing VLSI layout. Hypercube is one of the most significant interconnection networks in parallel computing systems. The exchanged hypercube is an important variant of the hypercube, which is obtained by systematically deleting edges from a hypercube. It not only retains several valuable and desirable properties of the hypercube, but also has lower hardware cost. In this paper, we first give an exact formula of minimum wirelength of exchanged hypercube layout into a grid. Furthermore, we propose an O(N) algorithm for embedding exchanged hypercube into a gird with load 1, expansion 1 and minimum wirelength and derive a linear layout of exchanged hypercube with minimum number of tracks and efficient layout areas. Finally, we present simulation experiments of our embedding algorithm on network overhead and total wirelength, which conduce to estimate the total wirelength and chip area. [ABSTRACT FROM AUTHOR]

With advancement in the nanometer era, more and more intellectual property (IP) blocks can be integrated on a single die. Network-on-chip (NoC) has emerged as a viable alternative to unplug the communication bottleneck in system-on-chip. In the NoC synthesis flow, IP block mapping problem is one of the holistic research problems, which aims to minimize the overall communication cost or power consumption of the network. Since mesh is a well-accepted topology, we focus on IP mapping problem onto mesh-based NoCs in this paper. The IP mapping problem is proven to be NP-hard. No exact algorithm is expected to solve it in the polynomial time, and considerable computation time is required for even small-scale instances. In this paper, we analyze the symmetry character in mesh and propose an adaptive memetic algorithm (AMA) to solve the application mapping problem. The novel AMA method integrates both global and local optimization techniques, which contributes to the effectiveness and efficiency of the algorithm. Experiments have been carried out under both real application and synthetic benchmarks. Experimental results indicate that the proposed AMA outperforms the existing heuristics (CastNet and genetic algorithm) in the aspects of solution quality and power consumption. Within acceptable time limit, AMA could obtain optimal or suboptimal solutions when compared with the exact algorithm. [ABSTRACT FROM AUTHOR]

As the scale of supercomputers grows, so does the size of the interconnect network. Topology-aware task mapping, which maps parallel application processes onto processors to reduce communication cost, becomes increasingly important. Previous works mainly focus on the task mapping between compute nodes (i.e., inter-node mapping), while ignoring the mapping within a node (i.e., intra-node mapping). In this paper, we propose a hierarchical task mapping strategy, which performs both inter-node and intra-node mapping. We consider supercomputers with popular fat-tree and torus network topologies, and introduce two mapping algorithms: (1) a generic recursive tree mapping algorithm, which can handle both inter-node mapping and intra-node mapping; (2) a recursive bipartitioning mapping algorithm for torus topology, which efficiently partitions the compute nodes according to their coordinates. Moreover, a hierarchical task mapping library is developed. Experimental results show that the proposed approach significantly improves the communication performance by up to 77 % with low runtime overhead. [ABSTRACT FROM AUTHOR]

The complete binary tree as an important network structure has long been investigated for parallel and distributed computing, which has many nice properties and used to be embedded into other interconnection architectures. The parity cube is an important variant of the hypercube. It has many attractive features superior to those of the hypercube. In this paper, we prove that the complete binary tree with $$2^n-1$$ vertices can be embedded with dilation 1, congestion 1, load 1 into the $$n$$ -dimensional parity cube $$PQ_n$$ and expansion tending to 1. Furthermore, we provide an $$O(NlogN)$$ algorithm to construct the complete binary tree with $$2^n-1$$ vertices in $$PQ_n$$ , where $$N$$ denotes the number of vertices in $$PQ_n$$ and $$n\ge 1$$ . [ABSTRACT FROM AUTHOR]

The balanced hypercube, proposed by Wu and Huang, is a new variation of hypercube. The particular property of the balanced hypercube is that each processor has a backup processor that shares the same neighborhood. A Hamiltonian bipartite graph with bipartition $$V_{0}\cup V_{1}$$ is said to be Hamiltonian laceable if there is a Hamiltonian path between any two vertices $$x\in V_{0}$$ and $$y\in V_{1}$$ . A graph $$G$$ is hyper-Hamiltonian laceable if it is Hamiltonian laceable and, for any vertex $$v\in V_{i}$$ , $$i\in \{0,1\}$$ , there is a Hamiltonian path in G- v between any pair of vertices in $$V_{1-i}$$ . In this paper, we mainly prove that the balanced hypercube is hyper-Hamiltonian laceable. [ABSTRACT FROM AUTHOR]

Mapping of parallel programs onto parallel computers for efficient execution is a fundamental problem of great significance in parallel processing. This paper presents an architecture-independent software tool for contention-free mapping of arbitrary parallel programs onto parallel computers with arbitrary configurations. This mapping tool is based on an efficient heuristic algorithm that runs in time O( n3+ m4) in the worst case for mapping n tasks onto m processors, where m ≪ n in most practical cases. It is fully implemented and incorporated into a graph editing system to produce a graphical mapping tool which enables its user to monitor and control the mapping process. The user can assist the mapping process or employ the algorithm to map automatically. Our mapping tool has been tested and its performance evaluated extensively. Experimental results show that our tool combines user intuition and mapping heuristics effectively to make it a powerful mapping tool which is practical to use. Our mapping tool can be easily extended for use in the more general case when the link contention-degree is bounded to a fixed system-specified value without increasing its complexity. [ABSTRACT FROM AUTHOR]