检索结果-内蒙古大学图书馆

Path Embedding in Faulty Locally Twisted Cubes

Path Embedding in Faulty Locally Twisted Cubes

2009 2nd IEEE International Conference on Computer Science and Information Technology(第二届计算机科学与信息技术国际会议 ICCSIT2009)

作者： Yuejuan Han Jianxi Fan Jiwen Yang Peide Qian School of Computer Science and Technology Soochow University Suzhou China

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, fault-tolerant embedding of paths in locally twisted cubes is studied. Let LTQn(V,E) denotes the n-dimensional locally twisted cube. We find that, for any faulty set F ? V (LTQn)∪E(LTQn) with ∣F∣≤n-3 and l with 2n-1-1 l≤l≤∣V (LTQn-F)∣-1 for any integer n≥3, a path of length l can be embedded between any two distinct nodes with dilation 1 in LTQn-F. And, the result does not hold if l≤2n-1-2 or ∣F∣≥n-2, that is, the two bounds are tight. Moreover, this result extends the known result on (n-3)-Hamiltonian connectivity of LTQn in the literature.

关键词： locally twisted cube fault-tolerant path embedding dilation parallel computing system

来源：评论

学校读者我要写书评

暂无评论

Efficient Algorithms to Embed Hamiltonian Paths and Cycles in Faulty Crossed Cubes

Efficient Algorithms to Embed Hamiltonian Paths and Cycles i...

引用

第四届国际计算机新科技与教育学术会议(2009 4th International Conference on Computer Science & Education)

作者： Jianxi Fan Wujun Zhou Yuejuan Han Guangquan Zhang School of Computer Science and Technology Soochow University Suzhou 215006 China

The crossed cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. Hamiltonicity is a critical property in interconnection networks. In this paper, we study fault-tolerant embedding algorithms of Hamiltonian paths and cycles in crossed cubes. We provide two algorithms HamiltonianPath and HamiltonianCycle. For any integer n ≥ 3, letting CQn(V,E) denote the n-dimensional crossed cubes and F (∩) V (CQn) ∪ E(CQn) denote a faulty set in CQn, (1) if |F| ≤ n-3, HamiltonianPath can construct a Hamiltonian path between any two distinct nodes in CQn -F in O(NlogN) time;and (2) if |F| ≤ n-2, Hamiltoniancycle can construct a Hamiltonian cycle in CQn-F in O(NlongN)time, where N is the node number of CQn-F.

关键词： Crossed cube fault-tolerant path embedding dilation parallel computing system

来源：评论

学校读者我要写书评

暂无评论

Edge-pancyclicity and path-embeddability of bijective connection graphs

引用

INFORMATION SCIENCES 2008年第2期178卷 340-351页

作者： Fan, Jianxi Jia, Xiaohua Qingdao Univ Coll Informat Engn Qingdao 266071 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

An n-dimensional Bijective Connection graph (in brief BC graph) is a regular graph with 2(n) nodes and n2(n-1) edges. The n-dimensional hypercube, crossed cube, Mobius cube, etc. are some examples of the n-dimensional BC graphs. In this paper, we propose a general method to study the edge-pancyclicity and path-embeddability of the BC graphs. First, we prove that a path of length l with dist(X-n, x, y) + 2 <= l <= 2(n) - 1 can be embedded between x and y with dilation 1 in X-n for x,y epsilon V(X-n) with x not equal y in X-n, where X-n (n >= 4) is a n-dimensional BC graph satisfying the three specific conditions and V(X-n) is the node set of X-n. Furthermore, by this result, we can claim that X-n is edge-pancyclic. Lastly, we show that these results can be applied to not only crossed cubes and Mobius cubes, but also other BC graphs except crossed cubes and Mobius cubes. So far, the research on edge-pancyclicity and path-embeddability has been limited in some specific interconnection architectures such as crossed cubes, Mobius cubes. (c) 2007 Elsevier Inc. All rights reserved.

关键词： bijective connection graph crossed cube Mobius cube graph embedding dilation edge-pancyclicity path parallel computing system

来源：评论

学校读者我要写书评

暂无评论

Optimal fault-tolerant embedding of paths in twisted cubes

引用

JOURNAL OF parallel AND DISTRIBUTED computing 2007年第2期67卷 205-214页

作者： Fan, Jianxi Lin, Xiaola Pan, Yi Jia, Xiaohua City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Sun Yat Sen Univ Coll Informat Sci & Technol Guangzhou Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let TQ(n)(V, E) denote the n-dimensional twisted cube. We prove that a path of length I can be embedded between any two distinct nodes with dilation 1 for any faulty set F subset of V(T Q(n)) boolean OR E(T Q(n)) with \F\ <= n - 3 and any integer l with 2(n-1) - 1 <= l <= \V (T Q(n) - F)\-1 (n >= 3). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l and faulty set size \F\ for a successful embedding are tight. That is, the result does not hold if l <= 2(n-1) - 2 or \F\ >= n - 2. We also extend the result on (n - 3) -Hamiltonian connectivity of T Q(n) in the literature. (C) 2006 Elsevier Inc. All rights reserved.

关键词： twisted cube fault tolerant path embedding dilation parallel computing system

来源：评论

学校读者我要写书评

暂无评论

Complete path embeddings in crossed cubes

引用

INFORMATION SCIENCES 2006年第22期176卷 3332-3346页

作者： Fan, Jianxi Jia, Xiaohua Lin, Xiaola City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China Sun Yat Sen Univ Coll Informat Sci & Technol Guangzhou Peoples R China

Crossed cubes are popular variants of hypercubes. In this paper, we study path embeddings between any two distinct nodes in crossed cubes. We prove two important results in the n-dimensional crossed cube: (a) for any two nodes, all paths whose lengths are greater than or equal to the distance between the two nodes plus 2 can be embedded between the two nodes with dilation 1;(b) for any two integers n >= 2 and l with 1 <= l <= [n+1/2] - 1, there always exist two nodes x and y whose distance is l, such that no path of length l + 1 can be embedded between x and y with dilation 1. The obtained results are optimal in the sense that the dilations of path embeddings are all 1. The results are also complete, because the embeddings of paths of all possible lengths between any two nodes are considered. (C) 2006 Elsevier Inc. All rights reserved.

关键词： interconnection network crossed cube graph embedding optimal embedding parallel computing system

来源：评论

学校读者我要写书评

暂无评论

Optimal task scheduling algorithm for cyclic synchronous tasks in general multiprocessor networks

引用

JOURNAL OF parallel AND DISTRIBUTED computing 2005年第3期65卷 261-274页

作者： Park, HJ Kim, BK Korea Adv Inst Sci & Technol Dept Elect Engn & Comp Sci Taejon 305701 South Korea

We develop an optimal task allocation and scheduling algorithm which minimizes the computing period for multiprocessor systems with general network structures considering task execution time and communication contentions and routing delays explicitly. We presented new ideas of scheduling: (i) individual start allowing overlapping two different iterations, (ii) the scheduling space and the scheduling graph representing feasible schedules, and (iii) the check-and-diffusion algorithm utilizing property of the start-time difference vs. the computing period. With concrete examples of scheduling spaces, segments, and scheduled for various multiprocessor network architectures, we showed that individual start reduces the computing period, and our algorithm can find the optimal computing period without exhaustive search. (c) 2004 Elsevier Inc. All rights reserved.

关键词： parallel computing system task allocation and scheduling computing period cyclic synchronous tasks scheduling space

来源：评论

学校读者我要写书评

暂无评论

RHiNET-2/SW: High-speed network switch implemented with parallel optical interconnection for parallel computing system

引用

ELECTRONICS AND COMMUNICATIONS IN JAPAN PART II-ELECTRONICS 2002年第6期85卷 1-10页

作者： Nishimura, S Kudoh, T Nishi, H Yamamoto, J Harasawa, K Fukuda, S Shikichi, Y Akutsu, S Hitachi Ltd Cent Res Lab RWCP Opt Interconnect Hitachi Lab Kokubunji Tokyo 1858601 Japan RWCP Tsukuba Res Ctr RWCP Parallel & Distributed Syst Architecture Lab Tsukuba Ibaraki 3520004 Japan Hitachi Commun Syst Inc Yokohama Kanagawa 2440003 Japan

We developed the RHiNET-2/SW high-speed network switch for a high-throughput parallel computing system consisting of optically interconnected distributed personal computers (PCs). RHiNET-2/SW enables high-throughput network switching (64 Gbit/s) by means of a switching LSI and eight pairs of synchronized parallel optical interconnection modules. To confirm the reliability of RHiNET 2/SW we measured its bit error rate (BER), which was less than 10(-11) (estimated value: 10(-20)). Five RHiNET-2/SWs and sixteen PC nodes can perform parallel computing. This result demonstrates the feasibility of optical interconnection in a high-speed, flexible network in a parallel computing system. (C) 2002 Wiley Periodicals, Inc.

关键词： optical interconnection parallel computing system network switch synchronized parallel data transmission

来源：评论

学校读者我要写书评

暂无评论

Optimal path embedding in crossed cubes

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED systemS 2005年第12期16卷 1190-1200页

作者： Fan, JX Lin, XL Jia, XH City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China Sun Yat Sen Univ Coll Informat Sci & Technol Guangzhou Guangdong Peoples R China

The crossed cube is an important variant of the hypercube. The n-dimensional crossed cube has only about half diameter, wide diameter, and fault diameter of those of the n-dimensional hypercube. Embeddings of trees, cycles, shortest paths, and Hamiltonian paths in crossed cubes have been studied in literature. Little work has been done on the embedding of paths except shortest paths, and Hamiltonian paths in crossed cubes. In this paper, we study optimal embedding of paths of different lengths between any two nodes in crossed cubes. We prove that paths of all lengths between [n+1/2] + 1 and 2(n) - 1 can be embedded between any two distinct nodes with a dilation of 1 in the n-dimensional crossed cube. The embedding of paths is optimal in the sense that the dilation of the embedding is 1. We also prove that [n+1/2] - 1 is the shortest possible length that can be embedded between arbitrary two distinct nodes with dilation 1 in the n-dimensional crossed cube.

关键词： crossed cube graph embedding optimal embedding interconnection network parallel computing system

来源：评论

学校读者我要写书评

暂无评论

An implementation scheme of PVM netwrok parallel computing

An implementation scheme of PVM netwrok parallel computing

引用

15th IEEE Canadian Conference on Electrical and Computer Engineering

作者： Li, XT Sun, JZ Chen, S Liu, Y Yu, C Wei, Z Tianjin Univ Sch Elect Informat Engn Tianjin 300072 Peoples R China

ISBN: (纸本)0780377818

Based on PVM, a very simple yet very practical system, which can be used to evaluate the performance of various parallel application algorithms, is presented. In the system, full intercommunication switchers and dual network adapters are introduced in computing nodes to add the independent communication channels. As a result the transmission speed of data is increased, the communication bandwidth is expanded, the traffic load is alleviated and the system performance is improved. A very complex parallel global illumination algorithm is used to test the practicability and efficiency of the system. The results obtained demonstrate that the system has good practicability and scalability.

关键词： PVM parallel computing system communication channels performance

来源：评论

学校读者我要写书评

暂无评论

An optimal scheduling algorithm for minimizing the computing period of cyclic synchronous tasks on multiprocessors

引用

JOURNAL OF systemS AND SOFTWARE 2001年第3期56卷 213-229页

作者： Park, HJ Kim, BK Korea Adv Inst Sci & Technol Dept Elect Engn Yusong Gu Taejon 305701 South Korea

We present an efficient optimal algorithm that schedules cyclic synchronous tasks into multiprocessors to minimize the computing period of iterative execution. Due to the rapid development of higher speed microprocessors and digital signal processors (DSPs), small-scale parallel embedded systems and on-chip parallel processors with a simple network structure became feasible for applications such as large-scale simulations and computation-intensive plant control systems that were previously executed by massively parallel computers. We consider cyclic synchronous tasks with communication overhead, which run on multiprocessors with a fully connected network. We suggest the computing period as the performance measure to maximize overall computation speed and the individual start policy that allows overlapping different iterations. The concepts and characteristics of the local period and the global period are also introduced. To solve the complex optimal scheduling problem in an efficient way, our algorithm uses a new spatial scheduling technique using the scheduling space which represents all possible start-time schedules in a multi-dimensional space. By using spatial searching and an enhanced branch-and-bound technique, the optimal schedule which minimizes the computing period can be found. The scheduling results for power plant simulation verify the practicality of our algorithm. (C) 2001 Elsevier Science Inc. All rights reserved.

关键词： parallel computing system cycle synchronous tasks optimal task scheduling computing period scheduling space schedulable area

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：