The hypercube is a widely-used interconnection architecture in parallel machine. In this paper, we propose a fault-tolerant algorithm that embeds the Fibonacci cube to the faulty hypercube. The algorithm proposed here...
详细信息
The hypercube is a widely-used interconnection architecture in parallel machine. In this paper, we propose a fault-tolerant algorithm that embeds the Fibonacci cube to the faulty hypercube. The algorithm proposed here uses the bit ordering method for embedding the Fibonacci cube to the faulty hypercube efficiently. Here the Fibonacci cube of order n, Γn, which can be embedded to the m-dimensional hypercube Hm, in the condition of m ≥ n - 1. These results show the congestion 2, load 1, dilation 2, and unbounded expansion 2m/fn. At the same time, we demonstrate that the algorithm can tolerate O(m2-n2 faults.
Embedding is of great importance in the applications of parallel computing. Every parallel application has its intrinsic communication pattern. The communication pattern graph is mapped into the topology of multiproce...
详细信息
Embedding is of great importance in the applications of parallel computing. Every parallel application has its intrinsic communication pattern. The communication pattern graph is mapped into the topology of multiprocessor structures so that the corresponding application can be executed. This paper proposes a novel algorithm for emulation a class of regular graphs in the faulty hypercube, including the Hamiltonian path, the Hamiltonian cycle, the linear array, the ring, the mesh, and the complete binary tree. First, to obtain the replaceable node of the faulty node, n faults can be tolerated with expansion 2, dilation 3, congestion 1, and load 1. Furthermore, our method is also extending the distributed fault-tolerant emulation of a class of regular graphs in hypercubes. Unlike many existing algorithm which are capable of embedding only type of graphs, our algorithm embeds the above graphs in a unified way. By the results, we can easily port the parallel algorithms developed for the structure of a class of regular graphs to hypercube. This methodology of embedding enables extremely high-speed parallel computation.
Embedded systems and wireless communications are two development trends for electronic devices. Many consumer electronics has been implemented as mobile devices. Power consumption issue is thus one major concern for t...
详细信息
Embedded systems and wireless communications are two development trends for electronic devices. Many consumer electronics has been implemented as mobile devices. Power consumption issue is thus one major concern for this type of equipment. In this paper, a flexible and portable Wi-Fi mobile storage device called WiDiSH is introduced and analyzed. WiDiSH is targeted as an extensible wireless mobile data sharing equipment. Several storage media can be dynamically attached to WiDiSH and accessed instantly by multiple Wi-Fi enabled devices. A prototype of WiDiSH has been implemented and evaluated from the perspective of power consumption in a systematic way. A power breakdown analysis is performed thoroughly on the measured data. In addition, a prediction with respect to a practical mobile device also indicates that it's feasible to realize such a device with the proposed architecture.
Broadcasting which is a primitive communication problem is to distribute the same message from a source node to all other nodes. This problem appears in applications such as matrix operations, database operation and t...
详细信息
In this paper, we study the linear layout problem of an incomplete hypercube by the embedding-in-book technique. An incomplete hypercube is a generalization of the hypercube in the sense that the number of nodes can b...
详细信息
In this paper, we study the linear layout problem of an incomplete hypercube by the embedding-in-book technique. An incomplete hypercube is a generalization of the hypercube in the sense that the number of nodes can be an arbitrary number. Embedding a graph in a book is to place nodes on the spine of a book and to draw the edges such that edges residing in a page do not cross. In this paper, we propose a scheme to embed an incomplete hypercube of 2 n + 2 m nodes, where n > m ges 0, with n - 1 pages, cumulative page width 2 n + 2 m - 3; and book width 2 n - 1 + 2 m - 1 for n > m > 0, 2 n-1 for n > m = 0. Moreover, this scheme can be applied to an arbitrary size of an incomplete hypercube
In this paper, we study the linear layout problem of the rectangular mesh by the embedding-in-book technique. Embedding a graph in a book is to place nodes on the spine of a book and to draw the edges such that edges ...
详细信息
Broadcasting which is a primitive communication problem is to distribute the same message from a source node to all other nodes. This problem appears in applications such as matrix operations, database operation and t...
详细信息
ISBN:
(纸本)0780391950
Broadcasting which is a primitive communication problem is to distribute the same message from a source node to all other nodes. This problem appears in applications such as matrix operations, database operation and transitive closure algorithms. The topology considered in this paper is the cube-connected cycle that demonstrates many attractive properties, such as high degree of regularity, symmetry and efficient computation. In this paper, we present a novel distributed broadcasting scheme for the cube-connected cycles, which is much simpler and requires only constant data included in each message and constant time to determine the neighbors to forward the message. Moreover, the time steps (i.e., the height of the broadcasting tree) taken by this algorithm is under diameter, which is optimal.
In this paper, we study the linear layout problem of the rectangular mesh by the embedding-in-book technique. Embedding a graph in a book is to place nodes on the spine of a book and to draw the edges such that edges ...
详细信息
ISBN:
(纸本)0780391950
In this paper, we study the linear layout problem of the rectangular mesh by the embedding-in-book technique. Embedding a graph in a book is to place nodes on the spine of a book and to draw the edges such that edges residing in a page do not cross. We propose a scheme to embed an h /spl times/ w rectangular mesh with two pages and book width Min(h,w)-1.
A neural network based controller is derived for a mobile manipulator to track the given trajectories in the workspace. The dynamics of the mobile manipulator is assumed to be unknown completely, and is learned on-lin...
详细信息
A neural network based controller is derived for a mobile manipulator to track the given trajectories in the workspace. The dynamics of the mobile manipulator is assumed to be unknown completely, and is learned on-line by the radial basis function network (RBFN) with weight adaptation rule derived from the Lyapunov function. Generally, a RBFN can be used to properly approximate a nonlinear function. However, there remains some approximation error inevitably in real application. An additional control input to suppress this kind of error source is also used. The proposed algorithm does not need a priori knowledge about the exact system dynamic parameters. Simulation results for a two-link manipulator on a differential-drive mobile platform are presented to show the effectiveness for uncertain system.
This paper describes an experimental stereo vision based motion planning system for humanoid robots. The goal is to automatically generate arm trajectories that avoid obstacles in unknown environments from high-level ...
详细信息
This paper describes an experimental stereo vision based motion planning system for humanoid robots. The goal is to automatically generate arm trajectories that avoid obstacles in unknown environments from high-level task commands. Our system consists of three components: 1) environment sensing using stereo vision with disparity map generation and on-line consistency checking, 2) probabilistic mesh modeling in order to accumulate continuous vision input, and 3) motion planning for the robot arm using RRTs (rapidly exploring random trees). We demonstrate results from experiments using an implementation designed for the humanoid robot H7.
暂无评论