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

Proceedings of the international symposium on parallel architectures, algorithms and Networks, I-SPAN 1999年 184-189页

作者： Mao, Li-Jen Deo, Narsingh Lang, Sheau-Dong Univ of Central Florida Orlando United States

The Minimum Spanning Tree (MST) problem with an added constraint that no node in the spanning tree has the degree more than a specified integer d, is known as the Degree-Constrained MST (d-MST) problem. Since computing the d-MST is NP-hard for every d in the range 2 &le d &le (n - 2) where n denotes the total number of nodes, several approximate algorithms have been proposed in the literature. We have previously proposed two approximate algorithms, TC-RNN and IR, for the d-MST problem. Our experimental results show that while the IR algorithm is faster, the TC-RNN algorithm consistently produces spanning trees with a smaller weight. In this paper, we propose a new algorithm, TC-NNC, which is an improved version of TC-RNN. Our experiments using randomly generated, weighted graphs as input demonstrate that the execution time of TC-NNC is smaller than that of TC-RNN, and is very close to that of IR. Further, the quality-of-solution of TC-NNC is better than that of IR and is very close to that of TC-RNN.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel selection algorithms with analysis on clusters

Parallel selection algorithms with analysis on clusters

引用

international symposium on parallel architectures, algorithms and Networks (ISPAN)

作者： A. Fujiwara H. Katsuki M. Inoue T. Masuzawa Department of Computer Science and Electronics Kyushu Institute of Technology Fukuoka Japan Nara Institute of Science and Technology Graduate School of Information Science Ikoma Nara Japan

We present three deterministic parallel selection algorithms with analysis on clusters. The first and second algorithms are proposed on the CGM (Coarse Grained Multicomputer) model. The first algorithm achieves optimality with respect to its computation time and runs in O(n/p) computation time and O(min(log p, log log n)) communication rounds if n/p/spl ges/p/sup /spl epsiv// for any /spl epsiv/>0, where n is the number of input elements and p is the number of processors. The second algorithm achieves optimality with respect to the number of communication rounds and runs in O(n/p log p) computation time and the constant number of communication rounds if n/p>p/sup /spl epsiv// for any /spl epsiv/>0. The third selection algorithm is a hybrid algorithm of the above two algorithms and suitable for practical cluster computing. The algorithms are implemented using PVM, and its experimental results are also presented.

关键词： Clustering algorithms Algorithm design and analysis

来源：评论

学校读者我要写书评

暂无评论

Generalized hierarchical completely-connected networks

Generalized hierarchical completely-connected networks

引用

international symposium on parallel architectures, algorithms and Networks (ISPAN)

作者： T. Takabatake E. Kaneko H. Ito Graduate School of Science and Technology Chiba University Chiba Japan Faculty of Engineering Chiba University Chiba Japan

A novel network structure called generalized Hierarchical Completely-Connected networks (HCC) is proposed, and its properties and features are evaluated. A set of the HCCs constructed by the proposed method includes some conventional hierarchical networks (then it is called generalized). The construction of an HCC is started from a basic block (a level-1 block) which consists of n nodes with a constant degree. Then a level-h (h/spl ges/2) block is constructed recursively by interconnecting any pair of macro nodes (n level-(h-1) blocks) completely. An HCC has the constant node degree regardless of increasing its size (the number of nodes). Furthermore, since an HCC has a hierarchically structured character and the feature of uniformity, a wide variety of inter-cluster connections are possible.

关键词： parallel architectures

来源：评论

学校读者我要写书评

暂无评论

Exploiting global structure for performance on clusters

Proceedings of the International Parallel Processing Symposi...

引用

Proceedings of the international parallel Processing symposium, IPPS 1999年 176-182页

作者： Donaldson, Stephen R. Hill, Jonathan M.D. Skillicorn, David B. Oxford Univ Oxford United Kingdom

Most parallel programming models for distributed-memory architectures are based on individual threads interacting via send and receive operations. We show that a more structured model, BSP, gains substantial performance improvements by exploiting the extra information implicit in its structure. In particular, each thread learns something about global state whenever it receives a message. This information can be used to modify its own behavior to improve collective use of the communication system. The programming model's semantics also provides implicit knowledge that can be exploited to increase performance. We show that these effects are useful at the application level by comparing the performance of BSP and MPI implementations of the NAS parallel benchmarks.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Evaluation of a semi-static approach to mapping dynamic iterative tasks onto heterogeneous computing systems

Proceedings of the International Symposium on Parallel Archi...

引用

Proceedings of the international symposium on parallel architectures, algorithms and Networks, I-SPAN 1999年 204-209页

作者： Kwok, Yu-Kwong Maciejewski, Anthony A. Siegel, Howard Jay Ghafoor, Arif Ahmad, Ishfaq Univ of Hong Kong Hong Kong

To minimize the execution time of an iterative application in a heterogeneous parallel computing environment, an appropriate mapping scheme is needed for matching and scheduling the subtasks of the application onto the processors. When some of the characteristics of the application subtasks are unknown a priori and will change from iteration to iteration during execution-time, a semi-static methodology can be employed, that starts with an initial mapping but dynamically decides whether to perform a remapping between iterations of the application, by observing the effects of these dynamic parameters on the application's execution time. The objective of this study is to implement and evaluate such a semi-static methodology. For analyzing the effectiveness of the proposed scheme, it is compared with two extreme approaches: a completely dynamic approach using a fast mapping heuristic and an ideal approach that uses a genetic algorithm on-line but ignores the time for remapping. Experimental results indicate that the semi-static approach outperforms the dynamic approach and is reasonably close to the ideal but infeasible approach.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

A Java Internet computing environment with effective configuration method

A Java Internet computing environment with effective configu...

引用

international symposium on parallel architectures, algorithms and Networks (ISPAN)

作者： Chun-Mok Chung Pil-Sup Shin Shin-Dug Kim Software Laboratory Information OBU LG Information and Communications Limited Seoul South Korea Parallel Processing System Laboratory Department of Computer Science Yonsei University Seoul South Korea

For an effective Internet based distributed parallel computing platform, Java-Internet Computing Environment (JICE) is designed and implemented with multithreading and remote method invocation mechanisms provided in Java. Specifically, JICE supports a shared memory system model for communication between any two nodes. Under the JICE, communication time is a major candidate of performance bottleneck. To reduce this communication overhead, a method of grouping is designed based on the optimal communication time. Communication performance given by grouping is evaluated through the analysis of execution time and verified via experiments. The results show that communication time can be reduced about 80% from executing some Java benchmarks on JICE.

关键词： Java Internet parallel processing Concurrent computing Computer networks Computer interfaces Power engineering computing Local area networks Computer science Magnetic heads

来源：评论

学校读者我要写书评

暂无评论

A randomized BSP/CGM algorithm for the maximal independent set problem

A randomized BSP/CGM algorithm for the maximal independent s...

引用

international symposium on parallel architectures, algorithms and Networks (ISPAN)

作者： A. Ferreira N. Schabanel CNRS-I3S-INRIA Sophia-Antipolis France URA CNRS 1398 LIP-ENS Lyon Lyon France

This paper presents a randomized parallel algorithm for the Maximal Independent Set problem. Our algorithm uses a BSP-like computer with p processors and requires that n+m/p=/spl Omega/(p) for a graph with 72 vertices and m edges. Under this scalability assumption, and after a preprocessing phase, it computes a maximal independent set after O(log p) communication rounds, with high probability, each round requiring linear computation time O(n+p/p). The preprocessing phase is deterministic and important in order to ensure that degree computations can be implemented efficiently. For this, we give an optimal parallel BSP/CGM algorithm to the p-quantiles search problem, which runs in O(m log p/p) time and a constant number of communication rounds, and could be of interest in its own right, as shown in the text.

关键词： User-generated content Phase change random access memory Algorithm design and analysis Computational modeling Concurrent computing parallel algorithms Sorting Nominations and elections System recovery Communication networks

来源：评论

学校读者我要写书评

暂无评论

Using SADTs to support irregular computational problems

Using SADTs to support irregular computational problems

引用

international symposium on parallel architectures, algorithms and Networks (ISPAN)

作者： J. Nash P. Dew M. Berzins School of Computer Studies University of Leeds Yorkshire UK

There are well defined methods for supporting regular problems with scalable performance, typified by the HPF language and the BSP model. Less well understood is the solution of more irregular problems, supporting complex shared data structures and task dependencies, and typically requiring dynamic load balancing to sustain high performance. It is demonstrated how the use of Shared Abstract Data Types (SADTs), together with an extended BSP cost model, can support irregular problems in a structured manner An SADT is an extension of a serial ADT which allows the concurrent invocation of its methods. A number of SADTs are used to implement a solution of the travelling salesman problem on the Cray T3D machine, and a description of the restructuring of a parallel CFD code using SADTs is provided, with initial results given for the Cray T3E.

关键词： Costs Computational fluid dynamics Microwave integrated circuits Concurrent computing Chromium parallel processing Computer networks Runtime Portable computers Costing

来源：评论

学校读者我要写书评

暂无评论

A task scheduling algorithm to package messages on distributed memory parallel machines

A task scheduling algorithm to package messages on distribut...

引用

international symposium on parallel architectures, algorithms and Networks (ISPAN)

作者： N. Fujimoto T. Baba T. Hashimoto K. Hagihara Osaka University Toyonaka Japan

In this paper, we report a performance gap between a schedule with good makespan on the task scheduling model and the corresponding parallel program on distributed memory parallel machines. The main reason is the software overhead in the interprocessor communication. Therefore, speedup ratios of schedules on the model do not well approximate to those of parallel programs on the machines. The purpose of the paper is to get a task scheduling algorithm that generates schedules with good approximation to the corresponding parallel program. For this purpose, we propose an algorithm BCSH that generates only bulk synchronous style schedules. In those schedules, computation phases and communication phases appear alternately. All interprocessor communications are done only in the latter phases, and thus the corresponding parallel programs can make better use of the message packaging technique easily. It reduces some software overheads of messages from a source processor to the same destination processor to almost one software overhead, and improves the performance of a parallel program significantly. Finally we show some results of performance comparisons between BCSH and Kruatrachue's algorithm DSH. The schedules by the latter are famous for their good makespans. However the approximations of ours are much better than those of Kruatrachue's.

关键词： Scheduling algorithm Packaging machines parallel machines Processor scheduling Delay Concurrent computing Software packages Approximation algorithms Aging Read only memory

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm for the degree-constrained minimum spanning tree problem using nearest-neighbor chains

A parallel algorithm for the degree-constrained minimum span...

引用

international symposium on parallel architectures, algorithms and Networks (ISPAN)

作者： Li-Jen Mao Narsingh Deo Sheau-Dong Lang School of Computer Science University of Central Florida Orlando FL USA

The Minimum Spanning Tree (MST) problem with an added constraint that no node in the spanning tree has the degree more than a specified integer d, is known as the Degree-Constrained MST (d-MST) problem. Since computing the d-MST is NP-hard for every d in the range 2/spl les/d/spl les/(n-2) where n denotes the total number of nodes, several approximate algorithms have been proposed in the literature. We have previously proposed two approximate algorithms, TC-RNN and IR, for the d-MST problem (L.J. Mao et al., 1997). Our experimental results show that while the IR algorithm is faster, the TC-RNN algorithm consistently produces spanning trees with a smaller weight. We propose a new algorithm, TC-NNC, which is an improved version of TC-RNN. Our experiments using randomly generated, weighted graphs as input, demonstrate that the execution time of TC-NNC is smaller than that of TC-RNN, and is very close to that of IR. Further, the quality-of-solution of TC-NNC is better than that of IR and is very close to that of TC-RNN.

关键词： parallel algorithms Tree graphs Polynomials Computer science Nearest neighbor searches Silicon compounds Approximation algorithms Traveling salesman problems NP-hard problem Additives

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：