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

A MODULAR IMPLEMENTATION OF data structures IN BULK-SYNCHRONOUS parallel ML

parallel PROCESSING LETTERS 2008年第1期18卷 39-53页

作者： Cava, Frederic Univ Paris Est LACL F-94000 Creteil France

A functional data-parallel language called BSML has been designed for programming Bulk-Synchronous parallel algorithms. Many sequential algorithms do not have parallel counterparts and many non-computer science researchers do not want to deal with parallel programming. In sequential programming environments, common data structures are often provided through reusable libraries to simplify the development of applications. A parallel representation of such data structures is thus a solution for writing parallel programs without suffering from disadvantages of all the features of a parallel language. In this paper we describe a modular implementation in BSML of some data structures and show how those data types can address the needs of many potential users of parallel machines who have so far been deterred by the complexity of parallelizing code.

关键词： BSP parallel Functional language parallel data structures

来源：评论

学校读者我要写书评

暂无评论

An Efficient Dual-Hierarchy t-SNE Minimization

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2022年第1期28卷 614-622页

作者： van de Ruit, Mark Billeter, Markus Eisemann, Elmar Delft Univ Technol Delft Netherlands Univ Leeds Leeds W Yorkshire England

t-distributed Stochastic Neighbour Embedding (t-SNE) has become a standard for exploratory data analysis, as it is capable of revealing clusters even in complex data while requiring minimal user input. While its run-time complexity limited it to small datasets in the past, recent efforts improved upon the expensive similarity computations and the previously quadratic minimization. Nevertheless, t-SNE still has high runtime and memory costs when operating on millions of points. We present a novel method for executing the t-SNE minimization. While our method overall retains a linear runtime complexity, we obtain a significant performance increase in the most expensive part of the minimization. We achieve a significant improvement without a noticeable decrease in accuracy even when targeting a 3D embedding. Our method constructs a pair of spatial hierarchies over the embedding, which are simultaneously traversed to approximate many N-body interactions at once. We demonstrate an efficient GPGPU implementation and evaluate its performance against state-of-the-art methods on a variety of datasets.

关键词： Minimization Runtime Complexity theory Kernel Three-dimensional displays Graphics processing units Force High dimensional data dimensionality reduction parallel data structures dual-hierarchy GPGPU

来源：评论

学校读者我要写书评

暂无评论

Support for efficient programming on the SB-PRAM

引用

INTERNATIONAL JOURNAL OF parallel PROGRAMMING 1998年第3期26卷 209-240页

作者： Grun, T Rauber, T Rohrig, J Univ Saarland Dept Comp Sci D-66041 Saarbrucken Germany Univ Halle Wittenberg Dept Comp Sci D-06099 Halle Germany

The SB-PRAM is a shared-memory parallel computer that has been designed according to the PRAM model from theoretical computer science. The SB-PRAM realizes a concurrent-read, concurrent-write PRAM where each processor can access the global memory in unit time. This article describes the programming environment of the SB-PRAM that enables a programmer to develop efficient and portable programs without dealing with architectural details of the machine. In particular, we discuss compiler and operating system issues and show that the runtime functions of the P4 environment((1)) and several parallel data structures can be implemented very efficiently by using special features of the SB-PRAM. In contrast to other parallel machines, the synchronization of processors and the management of concurrent accesses to the global memory only require a few machine instructions independent of the number of processors participating in the operation. This efficient implementation of the runtime system is the basis for good performance of many challenging applications.

关键词： UMA shared memory computer PRAM model P4 programming environment parallel prefix parallel data structures

来源：评论

学校读者我要写书评

暂无评论

A SCALABLE DESIGN FOR VLSI DICTIONARY MACHINES

MICROPROCESSING AND MICROPROGRAMMING

引用

MICROPROCESSING AND MICROPROGRAMMING 1995年第5-6期41卷 359-372页

作者： DUBOUX, T FERREIRA, A GASTALDO, M Laboratoire de l'Informatique du Parallélisme URA 1398 du CNRS Ecole Normale Supérieure de Lyon 69364 Lyon Cedex 07 France

Most of the proposed VLSI dictionary machines appearing in the literature were designed to fit in one chip only. If the number of acquired elements is larger than that of VLSI cells, another chip has to be designed and manufactured to take a larger dictionary into account. In this paper, we propose a new design for dictionary machines that assembles blocks of standard existing dictionary machines. Our machine is as efficient as the best machines described in the literature, with the enormous advantage of scaling up quite easily, with no degradation of its performance, by simply adding more and more standard blocks.

关键词： DICTIONARY MACHINE VLSI LOAD BALANCING parallel data structures

来源：评论

学校读者我要写书评

暂无评论

CASCADING DIVIDE-AND-CONQUER - A TECHNIQUE FOR DESIGNING parallel ALGORITHMS

引用

SIAM JOURNAL ON COMPUTING 1989年第3期18卷 499-532页

作者： ATALLAH, MJ COLE, R GOODRICH, MT NYU COURANT INST MATH SCINEW YORKNY 10012 JOHNS HOPKINS UNIV HOSP DEPT COMP SCIBALTIMOREMD 21218

Techniques for parallel divide-and-conquer are presented, resulting in improved parallel algorithms for a number of problems. The problems for which improved algorithms are given include segment intersection detection, trapezoidal decomposition, and planar point location. Efficient parallel algorithms are algo given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point. All of the algorithms presented run in $O(\log n)$ time with either a linear or a sublinear number of processors in the CREW PRAM model.

关键词： 68E05 68C05 68C25 arallel algorithms parallel data structures divide-and-conquer computational geometry fractional cascading visibility planar point location trapezoidal decomposition dominance intersection detection

来源：评论

学校读者我要写书评

暂无评论

Scalability analysis for conservative simulation of logical circuits

引用

VLSI DESIGN 1999年第3期9卷 219-235页

作者： Keller, J Rauber, T Rederlechner, B Fern Univ Hagen FB Informat LG Tech Informat 2 D-58084 Hagen Germany Univ Halle Wittenberg Inst Informat D-06099 Halle Germany Telekom Entwicklungszentrum Sudwest D-66123 Saarbrucken Germany

We investigate conservative parallel discrete event simulations for logical circuits on shared-memory multiprocessors. For a first estimation of the possible speedup, we extend the critical path analysis technique by partitioning strategies. To incorporate overhead due to the management of data structures, we use a simulation on an ideal parallel machine (PRAM). This simulation can be directly executed on the SB-PRAM prototype, yielding both an implementation and a basis for data structure optimizations. One of the major tools to achieve these optimizations is the SB-PRAM's hardware support for parallel prefix operations. Our reimplementation of the PTHOR program on the SB-PRAM yields substantially higher speedups than before.

关键词： discrete event simulation conservative parallel simulation parallel data structures critical path analysis shared-memory multiprocessor PRAM

来源：评论

学校读者我要写书评

暂无评论

Union and split operations on dynamic trapezoidal maps

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2000年第3-4期17卷 153-163页

作者： Teillaud, M INRIA F-06902 Sophia Antipolis France

We propose algorithms to perform two new operations on an arrangement of line segments in the plane, represented by a trapezoidal map: the split of the map along a given vertical line D, and the union of two trapezoidal maps computed in two vertical slabs of the plane that are adjacent through a vertical line D. The data structure we use is a modified Influence Graph, still allowing dynamic insertions and deletions of line segments in the map. The algorithms for both operations run in O(s(D) log n + log(2) n) time, where n is the number of line segments in the map, and so is the number of line segments intersected by D. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： dynamic algorithms randomized algorithms data structures parallel data structures trapezoidal map

来源：评论

学校读者我要写书评

暂无评论

INTERSECTING LINE SEGMENTS IN parallel WITH AN OUTPUT-SENSITIVE NUMBER OF PROCESSORS

引用

SIAM JOURNAL ON COMPUTING 1991年第4期20卷 737-755页

作者： GOODRICH, MT Johns Hopkins Univ Baltimore MD United States

An efficient parallel algorithm is given for constructing the arrangement of n line segments in the plane, i.e., the planar graph determined by the segment endpoints and intersections. This algorithm is efficient relative to three efficiency measures-it is an NC algorithm, it has a small time-processor product, and it is output-size sensitive. In particular, it runs in O(log n) time using O(n log n + k) processors, where k is the size of the output (which is OMEGA(n2) in the worst case). The algorithm does not receive the value of k as input, it determines it on-line. A method for solving an important special case of the segment arrangement problem is also shown, namely, when each input segment is parallel to one of the coordinate axes (i.e., iso-oriented). The algorithm for this problem runs in O(log n) time using an optimal O(n + k/log n) processors. The model of computation is the CREW PRAM model, where processor allocation must be explicit and global.

关键词： COMPUTATIONAL GEOMETRY LINE-SEGMENT INTERSECTION parallel ALGORITHMS parallel data structures PRAM MODEL

来源：评论

学校读者我要写书评

暂无评论

A METHOD FOR data ALLOCATION AND MANIPULATION IN HYPERCUBE COMPUTERS

引用

parallel COMPUTING 1993年第5期19卷 497-510页

作者： ABOELAZE, M LEE, DL Department of Computer Science York University 4700 Keele Street North York Ont. M3J 1P3 Canada

In this paper, we propose a method for distributing data of an N x N matrix in an n-hypercube multiprocessor with N = 2n processors (n is even). This method is capable of distributing data among the processors' local memories such that the processors have a parallel access to rows, columns, contiguous blocks, and distributed blocks of the matrix without memory conflict. In accessing data, each processor can read/write the required element based only on the processor number and the instance of the data structure to be accessed (row number, column number, or block number), thereby requiring no global communication for computing the addresses of the elements. We provide two techniques to permute the accessed data among the processors to accommodate applications with different computational structures. One technique maps the elements of any instance of the data structure into the processors in row-major order. The other technique maps neighboring elements into processors which are hypercube-neighbors. We present simulation results for the delay for these two techniques using fixed and random scanning of the control vector, in a circuit switching and packet switching modes.

关键词： HYPERCUBE COMPUTERS CONFLICT-FREE data ACCESS parallel data structures ROUTING ALGORITHMS

来源：评论

学校读者我要写书评

暂无评论

A parallel priority queue with constant time operations

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 1998年第1期49卷 4-21页

作者： Brodal, GS Traff, JL Zaroliagis, CD Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Aarhus Dept Comp Sci BRICS DK-8000 Aarhus C Denmark

We present a parallel priority queue that supports the following operations in constant time: parallel insertion of a sequence of elements ordered according to key, parallel decrease key for a sequence of elements ordered according to key, deletion of the minimum key element, and deletion of an arbitrary element. Our data structure is the first to support multi-insertion and multi-decrease kev in constant time. The priority queue can be implemented on the EREW PRAM and can perform any sequence of n operations in O(n) time and O(m log n) work, m being the total number of keyes inserted and/or updated. A main application is a parallel implementation of Dijkstra's algorithm for the single-source shortest path problem, which runs in O(n) time and O(m log n) work on a CREW PRAM on graphs with n vertices and m edges. This is a logarithmic factor improvement in the running time compared with previous approaches. (C) 1998 Academic Press.

关键词： parallel data structures parallel algorithms graph algorithms priority queues

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：