Optimal parallelalgorithms, the analog of linear-time sequential algorithms, are defined. Optimal parallelalgorithms are known for several trivial computational tasks for which linear-time sequential algorithms are ...
详细信息
ISBN:
(纸本)0444876626
Optimal parallelalgorithms, the analog of linear-time sequential algorithms, are defined. Optimal parallelalgorithms are known for several trivial computational tasks for which linear-time sequential algorithms are immediate. Optimal parallelalgorithms for Selection and String Matching are sketched. Surprisingly these are currently the only two known optimal parallelalgorithms for problems for which linear-time sequential algorithms are not immediate.
parallelalgorithms are given for finding a maximum clique, maximum independent set, a minimum clique cover, and a minimum dominating set of an interval graph. parallelalgorithms are also given for finding a Hamilton...
详细信息
ISBN:
(纸本)0444876626
parallelalgorithms are given for finding a maximum clique, maximum independent set, a minimum clique cover, and a minimum dominating set of an interval graph. parallelalgorithms are also given for finding a Hamiltonian circuit and the minimum bandwidth of a proper interval graph. The shared memory model (SMM) of parallel computers is used to obtain fast algorithms.
We present algorithms for scheduling a system of n unit-length tasks on m identical parallel machines for the case where the precedence constraints are a collection of outtrees. The given algorithms produce an optimal...
详细信息
ISBN:
(纸本)0444876626
We present algorithms for scheduling a system of n unit-length tasks on m identical parallel machines for the case where the precedence constraints are a collection of outtrees. The given algorithms produce an optimal height-priority schedule on an exclusive read, exclusive write (EREW) P-RAM. The complexity of these algorithms is either O((logn)**2) parallel time using O(n) processors, or O(logn) parallel time and O(n**2) processors. As a complementary result we prove that finding a height-priority-schedule for the same problem is logspace complete for P, if the number of available machines is allowed to increase with time.
Many popular theoretical parallel machine models suffer the drawback of being highly impractical. The aim of this paper is to examine simulations of two impractical parallel machine models (global memory machines and ...
详细信息
ISBN:
(纸本)0444876626
Many popular theoretical parallel machine models suffer the drawback of being highly impractical. The aim of this paper is to examine simulations of two impractical parallel machine models (global memory machines and networks of sequential processors) by two practical models (uniform circuits and feasible networks). A single basic theorem is given which unifies current research in this area. As a corollary we obtain improved simulations of space and reversal bounded Turing machines by width and depth bounded uniform circuits.
The architecture of a small programmable parallel machine is described. The machine consists of a rectangular mesh of processing elements, interconnected via horizontal, vertical and diagonal buses. The processing ele...
详细信息
ISBN:
(纸本)0444876626
The architecture of a small programmable parallel machine is described. The machine consists of a rectangular mesh of processing elements, interconnected via horizontal, vertical and diagonal buses. The processing elements can either connect or disconnect the bus in any of the four directions at each step of the computation. In effect, the bus structure can be dynamically reconfigured under program control. The main application envisioned for this parallel machine is the implementation of an arithmetic and logic unit (ALU) for a conventional computer. Rather than designing the ALU with separate units such as adders, shifters and multipliers, it will consist of uniform general purpose parallel hardware which can be reconfigured into the appropriate structure under the direction of a microprogram.
The technological progress achieved during the last two decades in the design and manufacture of integrated circuits is forcing upon us a reexamination of the architecture of modern computers. The technology which wil...
详细信息
ISBN:
(纸本)0444876626
The technological progress achieved during the last two decades in the design and manufacture of integrated circuits is forcing upon us a reexamination of the architecture of modern computers. The technology which will be industrially available in the near future allows us to consider the building of machines made of silicon chips containing a few million transistors each. Such machines should be far more powerful than the largest computers existing today. The successful development and fabrication of such complex physical devices require that they be constructed in a highly repetitive manner from very simple atomic structures. Techniques of redundancy allow automatic detection of defective components. Such machines have a structure which is physically static and allows massive parallelism. Seen from the software user, these same machines must show a different face: they are dynamic information structures which can be arbitrarily modified in order to adapt them to the immense diversity of sequential and parallel software existing today, and to be developed in the future.
This conference proceedings contains 50 papers, of which 2 are given in abstract form only. The topics covered are: SIMD architecture;algorithms and applications;multiprocessor systems;VLSI architecture;parallel archi...
详细信息
This conference proceedings contains 50 papers, of which 2 are given in abstract form only. The topics covered are: SIMD architecture;algorithms and applications;multiprocessor systems;VLSI architecture;parallelarchitectures;pictorial database systems;and special applications. Technical and professional papers from this conference are indexed with the conference code no. 00341 in the Ei Engineering Meetings (TM) database produced by Engineering Information, Inc.
This two volume set LNCS 8630 and 8631 constitutes the proceedings of the 14th international Conference on algorithms and architectures for parallel Processing, ICA3PP 2014, held in Dalian, China, in August 2014. The ...
详细信息
ISBN:
(数字)9783319111940
ISBN:
(纸本)9783319111933
This two volume set LNCS 8630 and 8631 constitutes the proceedings of the 14th international Conference on algorithms and architectures for parallel Processing, ICA3PP 2014, held in Dalian, China, in August 2014. The 70 revised papers presented in the two volumes were selected from 285 submissions. The first volume comprises selected papers of the main conference and papers of the 1st internationalworkshop on Emerging Topics in Wireless and Mobile Computing, ETWMC 2014, the 5th internationalworkshop on Intelligent Communication Networks, IntelNet 2014, and the 5th internationalworkshop on Wireless Networks and Multimedia, WNM 2014. The second volume comprises selected papers of the main conference and papers of the workshop on Computing, Communication and Control Technologies in Intelligent Transportation System, 3C in ITS 2014, and the workshop on Security and Privacy in Computer and Network Systems, SPCNS 2014.
is the proceedings of the third Austrian-Hungarian workshop on Distributed and parallel Systems organized jointly by the Austrian Computer Society and the MTA SZTAKI Computer and Automation Research Institute. This...
详细信息
ISBN:
(数字)9781461544890
ISBN:
(纸本)9780792378921;9781461370239
is the proceedings of the third Austrian-Hungarian workshop on Distributed and parallel Systems organized jointly by the Austrian Computer Society and the MTA SZTAKI Computer and Automation Research Institute. This book contains 18 full papers and 12 short papers from 14 countries around the world, including Japan, Korea and Brazil. The paper sessions cover a broad range of research topics in the area of parallel and distributed systems, including software development environments, performance evaluation, architectures, languages, algorithms, web and cluster computing.;This volume will be useful to researchers and scholars interested in all areas related to parallel and distributed computing systems.
This two volume set LNCS 8630 and 8631 constitutes the proceedings of the 14th international Conference on algorithms and architectures for parallel Processing, ICA3PP 2014, held in Dalian, China, in August 2014. The ...
详细信息
ISBN:
(数字)9783319111971
ISBN:
(纸本)9783319111964
This two volume set LNCS 8630 and 8631 constitutes the proceedings of the 14th international Conference on algorithms and architectures for parallel Processing, ICA3PP 2014, held in Dalian, China, in August 2014. The 70 revised papers presented in the two volumes were selected from 285 submissions. The first volume comprises selected papers of the main conference and papers of the 1st internationalworkshop on Emerging Topics in Wireless and Mobile Computing, ETWMC 2014, the 5th internationalworkshop on Intelligent Communication Networks, IntelNet 2014, and the 5th internationalworkshop on Wireless Networks and Multimedia, WNM 2014. The second volume comprises selected papers of the main conference and papers of the workshop on Computing, Communication and Control Technologies in Intelligent Transportation System, 3C in ITS 2014, and the workshop on Security and Privacy in Computer and Network Systems, SPCNS 2014.
暂无评论