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

Solving the facility location and design (1|1)-centroid problem via parallel algorithms

JOURNAL OF SUPERCOMPUTING 2011年第3期58卷 420-428页

作者： Redondo, J. L. Fernandez, J. Garcia, I. Ortigosa, P. M. Univ Almeria Dpt Comp Architecture & Elect Almeria Spain Univ Malaga Dpt Comp Architecture & Elect E-29071 Malaga Spain Univ Murcia Dpt Stat & Operat Res Murcia Spain

Several parallel strategies for solving a centroid problem are presented. In the competitive location problem considered in this paper, the aim is to maximize the profit obtained by a chain (the leader) knowing that a competitor (the follower) will react by locating another single facility after the leader locates its own facility. A global optimization memetic algorithm called UEGO_*** was proposed to cope with this hard-to-solve optimization problem. Now, five parallel implementations of the optimization algorithm have been developed. The use of several processors, and hence more computational resources, allows us to solve bigger problems and to implement new methods which increase the robustness of the algorithm at finding the global optimum. A computational study comparing the new parallel methods in terms of efficiency and effectiveness has been carried out.

关键词： parallelism Master-slave Coarse-grain Evolutionary algorithm Nonlinear bilevel programming problem Centroid (or Stackelberg) problem

来源：评论

学校读者我要写书评

暂无评论

MULTIPLUS/MULPLIX parallel processing environment

MULTIPLUS/MULPLIX parallel processing environment

引用

Proceedings of the 1996 2nd international symposium on parallel architectures, algorithms, and Networks, I-SPAN

作者： Aude, J.S. Meslin, A.M. Santos, C.M.P. Bronstein, G. Cordeiro, L.F.M. Barros, M.O. Joao Jr., M. Oliveira, S.C. Federal Univ of Rio de Janeiro Rio de Janeiro Brazil

The MULTIPLUS project aims at the development of a modular parallel architecture suitable for the study of several aspects of parallelism in both true shared memory and virtual shared memory environments. The MULTIPLUS architecture is able to support up to 1024 Processing Elements based on SPARC microprocessors. The MULPLIX Unix-like operating system offers a suitable parallel programming environment for the MULTIPLUS architecture by providing facilities for the creation of threads, the allocation of private and shared memory space and the efficient use of synchronization primitives. After presenting the main features of the MULTIPLUS architecture and of the MULPLIX operating system, the paper describes in detail the design and the implementation of the three MULTIPLUS architecture basic hardware modules: the Processing Element, the Multistage Interconnection Network and the I/O Processor. In addition, the definition of the MULPLIX parallel programming primitives is discussed and their use is illustrated through an example. Finally, future directions in the development of the MULTIPLUS research project are commented.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Packed exponential connections network

Packed exponential connections network

引用

Proceedings of the 1996 2nd international symposium on parallel architectures, algorithms, and Networks, I-SPAN

作者： Quammen, Donna Stanley, James Wang, Pearl Y. George Mason Univ Fairfax United States

PEC (Packed Exponential Connections) is a scalable interconnection network for parallel systems that meets many requirements for a large range of system sizes, i.e. from 16 to over 1,000,000 processors. A scalable network architecture must meet the following criteria: have a low average and maximum diameter to avoid communication latency;minimize routing contentions;have a constant number of ports per node and a simple wire layout to allow for expansion;be inherently fault tolerant;be subdividable for disjoint multi-user applications;and be able to handle a large range of algorithm implementations without adding undo overhead. Our initial research has shown that PEC can meet each of the above criteria within acceptable limits. Further investigation is required to confirm these preliminary results.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT parallel algorithms FOR FUNCTIONAL DEPEndENCY MANIPULATIONS 90

引用

2nd international SYMP ON DATABASES IN parallel And DISTRIBUTED SYSTEMS ( DPDS 90 )

作者： SRIDHAR, R IYENGAR, SS Department of Computer Science Louisiana State University Baton Rouge LA

ISBN: (纸本)0818620528

Given a set of functional dependencies Σ and a single dependency σ, we show that the algorithm to test whether Σ implies σ is log-space complete in P. The functional dependencies Σ are represented as a directed hypergraph HΣ [1]. We first present a parallel algorithm which solves the above implication problem using P processors on a EREW-PRAM in Ο(e/P + ***) time and on a CRCW-PRAM in Ο(e/P + n) time, where e and n are the number of arcs and nodes of the graph HΣ. For graphs HΣ with fixed degree and diameter, we show that the closure HΣ+ can be computed in NC. We present NC algorithms to obtain a non-redundant and a LR-Minimum cover for the set of functional dependencies Σ. All our algorithms on a n-node directed hypergraph with fixed degree and diameter can be implemented to run in Ο(log2n) time with M(n) processors on a CREW-PRAM model, where M(n) is the cost of multiplying two binary matrices. The algorithms are efficient based on the transitive closure bottleneck phenomenon [7] that is, any improvement in the time and processor complexity of the transitive closure algorithm will result in an improvement by the same amount for the algorithms presented here.

关键词： functional dependency processor complexity minimal cover directed hyper-graph parallel algorithm log-space reduction NC algorithm time complexity non-redundant cover relational databases minimum cover

来源：评论

学校读者我要写书评

暂无评论

A new parallel algorithm for the parentheses-matching problem

A new parallel algorithm for the parentheses-matching proble...

引用

aizu international symposium on parallel algorithms/architecture synthesis

作者： L. Bergogne C. Cerin Université de Picardie Jules-Verne Amiens France

The parentheses-matching problem is of crucial importance in the construction of expression tree in order to evaluate, for instance, arithmetic expressions. A new parallel algorithm is introduced in this paper to solve the parentheses-matching problem optimally (in O(log/sub 2/ n) parallel time with O(n/log/sub 2/ n) processors) on an EREW-PRAM model. An algorithm for an input string of n parentheses with a maximal nested level of log n is also presented.

关键词： parallel algorithms Phase change random access memory Arithmetic Formal languages Data structures Tree data structures Calculus Impedance matching

来源：评论

学校读者我要写书评

暂无评论

Framework for automated software partitioning and mapping for distributed multiprocessors

Framework for automated software partitioning and mapping fo...

引用

Proceedings of the 1996 2nd international symposium on parallel architectures, algorithms, and Networks, I-SPAN

作者： Ramanujan, Ranga S. Bonney, Jordan C. Thurber, Kenneth J. Jha, Rakesh Siegel, Howard Jay Architecture Technology Corp Minneapolis United States

One of the major impediments to the widespread use of large-scale, distributed memory multiprocessors is the difficulty of efficiently partitioning and mapping application algorithms onto these machines so as to extract a large portion of the machines' peak performance. In this paper, we present the preliminary accomplishments of an ongoing effort aimed at automating the complex tasks of software partitioning and mapping during the system definition phase of application development for distributed memory multiprocessors. We describe a technique called the Augmented Task Dependency Graph (ATDG) for representing the high-level design of the application software. The ATDG allows one to express functional parallelism as well as data parallelism in a manner that facilitates automated partitioning and mapping. We propose a new strategy for searching through the possible space of design choices for partitioning and mapping. The proposed approach, called hierarchical hybrid search, organizes the search space as a hierarchy of sub-spaces. It permits the use of different search techniques for searching through different search sub-spaces. Examples of search techniques that could be employed in the proposed approach include hill-climbing, simulated annealing, and genetic algorithms.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Communication algorithms on alternating group graphs

Communication algorithms on alternating group graphs

引用

aizu international symposium on parallel algorithms/architecture synthesis

作者： Chih-Ming Lai Jyh-Jong Tsay Department of Computer Science and Information Engineering National Chung Cheng University Chiayi Taiwan

ISBN: (纸本)0818678704

We study the problem of performing all-to-all broadcast on an n-alternating group graph AG/sub n/ with all-port and store-and-forward routing. The running time is [(n/sup 1/-2)/(4(n-2))+1] that is one step more than the trivial lower bound [(n/sup 2/-2)/(4(n-2))]. Our algorithm is based on some new properties of Hamiltonian paths of AG/sub n/ that are identified in this paper and are of independent interest. Similar properties have been used to design an algorithm for single-node scattering that achieves the same time bound.

关键词： Broadcasting Scattering Distributed computing Concurrent computing Hypercubes Routing Computer science Memory architecture parallel processing Councils

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm for k-minimum spanning trees

A parallel algorithm for k-minimum spanning trees

引用

aizu international symposium on parallel algorithms/architecture synthesis

作者： Jun Ma K. Iwama Qian-Ping Gu Department of Computer Science Shandong University Jinan China Department of Computer Science and Communication Engineering Kyushu University Fukuoka Japan Department of Computer Software University of Aizu Wakamatsu Japan

ISBN: (纸本)0818678704

A parallel algorithm to find k, 2/spl les/k/spl les/n/sup n-2/, spanning trees from a connected, weighted and undirected graph C(V, E, W) in the order of increasing weight is presented. It runs in O(T(n)+klogn) time with O(n/sup 2//log n) processors on a CREW PRAM, where n=|V|, m=|E| and T(n), O(log n)/spl les/T(n)/spl les/O(log/sup 2/ n), is the time of the fastest parallel algorithms to find a minimum spanning tree of G on a CREW PRAM with no more than O(n/sup 2//log n) processors. Since T(n)=O(log/sup 2/ n) for the time being, this result shows that to find k minimum spanning trees can be done in the same time bound as to find just one when k/spl les/O(log n) on a CREW PRAM.

关键词： parallel algorithms Tree graphs Phase change random access memory Computer science Software Concrete Algorithm design and analysis Terminology

来源：评论

学校读者我要写书评

暂无评论

2nd international symposium on High Performance Computing, ISHPC 1999

引用

2nd international symposium on High Performance Computing, ISHPC 1999

ISBN: (纸本)3540659692

The proceedings contain 41 papers. The special focus in this conference is on System architecture and System Software. The topics include: An introduction to DRAMA project;an introduction to OCEANS project;an introduction to NANOS project;synchronous communication of molecular and electronic structure information in a distributed computing environment;profile-based selection of load value and address predictors;instruction-level microprocessor modeling of scientific applications;neural network classifiers execution on superscalar microprocessors;coping with very high latencies in petaflop computer systems;parallelization via constrained storage mapping optimization;a comparison of automatic parallelizing compiler and improvements by compiler directives;dynamically adaptive parallel programs;a feasibility study in iterative compilation;multithreading runtime support for loop and functional parallelism;parallelization and vectorization effects on a code simulating a vitreous lattice model with constrained dynamics;multi-phase hydrodynamic simulations on parallel computer;the case for a practical approach to performance prediction;evaluation of parallel form factor calculations and a static load balancing algorithm;parallel distributed optimization by resource addition and reduction;application of parallel sparse direct methods in semiconductor device and process simulation;integrity and performance in network attached storage;basic design of the earth simulator;high-performance parallel fem for geophysical applications;a graphics tool for the synthesis of automatic and user-driven program parallelization in the compilation process;parallel map recognition by pipeline control;a parallel programming environment for networks and emulation facility for data-driven real-time multi-processing.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel and distributed topological sort algorithms

Efficient parallel and distributed topological sort algorith...

引用

aizu international symposium on parallel algorithms/architecture synthesis

作者： J. Ma K. Iwama T. Takaoka Qian-Ping Gu The Department of Computer Science and Communication Engineering Kyushu University Fukuoka Japan Department of Computer Scienc Ibaraki University Hitachi Japan Department of Computer Software University of Aizu Fukushima Japan DepartmentComputer Science Shandong University Jinan China

In this paper, we give efficient parallel and distributed algorithms for the topological sort problem on acyclic graphs with n vertices. Our parallel algorithm solves the problem on a CREW PRAM in O(log/sup 2/ n) time with O(M(n)/log n) processors, where M(n) denotes the number of processors needed to multiply two n/spl times/n integer matrices over the integer ring. The best known upper bound of M(n) is O(n/sup 2.376/). The parallel algorithm can also solve the problem on processor arrays with reconfigurable bus systems in O(1) time and O(n/sup 3/) processors. Our distributed algorithm solves the topological sort problem of an arbitrary asynchronous network with communication complexity O(n/sup 2/).

关键词： Phase change random access memory Upper bound Shortest path problem Computer science Distributed algorithms Software Computational modeling Distributed computing Complexity theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：