Thu, 07 Aug 2008 21:24:23 BST CiteULike: AbnerCYH's parallel http://www.citeulike.org/user/AbnerCYH/tag/parallel CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/AbnerCYH/article/3088509 <i>Complexity, Vol. 9999, No. 9999. (2008), NA.</i><br /><br />Complex data sets are often unmanageable unless they can be subdivided and simplified in an intelligent manner. Clustering is a technique that is used in data mining and scientific analysis for partitioning a data set into groups of similar or nearby items. Hierarchical clustering is an important and well-studied clustering method involving both top-down and bottom-up subdivisions of data. In this article we address the parallel complexity of hierarchical clustering. We describe known sequential algorithms for top-down and bottom-up hierarchical clustering. The top-down algorithm can be parallelized, and when there are n points to be clustered, we provide an O(log n)-time, n2-processor Crew Pram algorithm that computes the same output as its corresponding sequential algorithm. We define a natural decision problem based on bottom-up hierarchical clustering, and add this HIERARCHICAL CLUSTERING PROBLEM (HCP) to the slowly growing list of CC-complete problems, thereby showing that HCP is one of the computationally most difficult problems in the COMPARATOR CIRCUIT VALUE PROBLEM class. This class contains a variety of interesting problems, and now for the first time a problem from data mining as well. By proving that HCP is CC-complete, we have demonstrated that HCP is very unlikely to have an NC algorithm. This result is in sharp contrast to the NC algorithm which we give for the top-down sequential approach, and the result surprisingly shows that the parallel complexities of the top-down and bottom-up approaches are different, unless CC equals NC. In addition, we provide a compendium of all known CC-complete problems. © 2008 Wiley Periodicals, Inc. Complexity, 2008 On the parallel complexity of hierarchical clustering and CC-complete problems Raymond Greenlaw Sanpawat Kantabutra doi:10.1002/cplx.20238 Complexity, Vol. 9999, No. 9999. (2008), NA. 2008-08-05T16:26:19-00:00 2008 Complexity 9999 9999 NA complexity kdd parallel http://www.citeulike.org/user/AbnerCYH/article/3084861 <i>(31 October 2007)</i><br /><br />"I hope that readers will learn to use the full expressibility and power of OpenMP. This book should provide an excellent introduction to beginners, and the performance section should help those with some experience who want to push OpenMP to its limits." --from the foreword by **David J. Kuck**, Intel Fellow, Software and Solutions Group, and Director, Parallel and Distributed Solutions, Intel Corporation OpenMP, a portable programming interface for shared memory parallel computers, was adopted as an informal standard in 1997 by computer scientists who wanted a unified model on which to base programs for shared memory systems. OpenMP is now used by many software developers; it offers significant advantages over both hand-threading and MPI. Using OpenMP offers a comprehensive introduction to parallel programming concepts and a detailed overview of OpenMP. _Using OpenMP_ discusses hardware developments, describes where OpenMP is applicable, and compares OpenMP to other programming interfaces for shared and distributed memory parallel architectures. It introduces the individual features of OpenMP, provides many source code examples that demonstrate the use and functionality of the language constructs, and offers tips on writing an efficient OpenMP program. It describes how to use OpenMP in full-scale applications to achieve high performance on large-scale architectures, discussing several case studies in detail, and offers in-depth troubleshooting advice. It explains how OpenMP is translated into explicitly multithreaded code, providing a valuable behind-the-scenes account of OpenMP program performance. Finally, _Using OpenMP_ considers trends likely to influence OpenMP development, offering a glimpse of the possibilities of a future OpenMP 3.0 from the vantage point of the current OpenMP 2.5. With multicore computer use increasing, the need for a comprehensive introduction and overview of the standard interface is clear. _Using OpenMP_ provides an essential reference not only for students at both undergraduate and graduate levels but also for professionals who intend to parallelize existing codes or develop new parallel programs for shared memory computer architectures. Using OpenMP: Portable Shared Memory Parallel Programming (Scientific and Engineering Computation) Barbara Chapman Gabriele Jost Ruud van der Pas (31 October 2007) 2008-08-05T10:32:56-00:00 2007 The MIT Press parallel http://www.citeulike.org/user/AbnerCYH/article/2627756 <i>Cluster Computing, 2003. Proceedings. 2003 IEEE International Conference on (2003), pp. 300-307.</i><br /><br />This paper addresses the problem of parallel transposition of large out-of-core arrays. Although algorithms for out-of-core matrix transposition have been widely studied, previously proposed algorithms have sought to minimize the number of I/O operations and the in-memory permutation time. We propose an algorithm that directly targets the improvement of overall transposition time. The I/O characteristics of the system are used to determine the read, write and communication block sizes such that the total execution time is minimized. We also provide a solution to the array redistribution problem for arrays on disk. The solution to the sequential transposition problem and the parallel array redistribution problem are then combined to obtain an algorithm for the parallel out-of-core transposition problem. Efficient parallel out-of-core matrix transposition S Krisnamoorthy G Baumgartner D Cociorva Chi-Chung Lam P Sadyappan doi:10.1109/CLUSTR.2003.1253328 Cluster Computing, 2003. Proceedings. 2003 IEEE International Conference on (2003), pp. 300-307. 2008-04-03T19:35:51-00:00 2003 Cluster Computing, 2003. Proceedings. 2003 IEEE International Conference on 300 307 algorithms data_structure parallel http://www.citeulike.org/user/AbnerCYH/article/2625760 <i>(2002), pp. 713-722.</i> Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms Seth Pettie Vijaya Ramachandran (2002), pp. 713-722. 2008-04-03T11:01:40-00:00 2002 713 722 Society for Industrial and Applied Mathematics algorithms graph parallel http://www.citeulike.org/user/AbnerCYH/article/2625759 <i>SIAM J. Comput., Vol. 31, No. 6. (2002), pp. 1879-1895.</i> A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest Seth Pettie Vijaya Ramachandran doi:10.1137/S0097539700371065 SIAM J. Comput., Vol. 31, No. 6. (2002), pp. 1879-1895. 2008-04-03T11:01:35-00:00 2002 SIAM J. Comput. 0097-5397 31 6 1879 1895 Society for Industrial and Applied Mathematics algorithms graph parallel stochastic http://www.citeulike.org/user/AbnerCYH/article/2625042 <i>SIAM Journal on Computing, Vol. 28, No. 1. (1998), pp. 105-136.</i> Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems Thomas Cormen Thomas Sundquist Leonard Wisniewski SIAM Journal on Computing, Vol. 28, No. 1. (1998), pp. 105-136. 2008-04-03T03:38:08-00:00 1998 SIAM Journal on Computing 28 1 105 136 SIAM algorithms complexity data_structure parallel http://www.citeulike.org/user/AbnerCYH/article/2624181 <i>(1996), pp. 128-139.</i> Structured permuting in place on parallel disk systems Leonard Wisniewski doi:10.1145/236017.236047 (1996), pp. 128-139. 2008-04-02T18:18:07-00:00 1996 128 139 ACM algorithms parallel sys_performance http://www.citeulike.org/user/AbnerCYH/article/2588835 <i>SIAM Journal on Computing, Vol. 18, No. 2. (1989), pp. 419-427.</i> A New Parallel Algorithm for the Maximal Independent Set Problem Mark Goldberg Thomas Spencer SIAM Journal on Computing, Vol. 18, No. 2. (1989), pp. 419-427. 2008-03-26T09:21:01-00:00 1989 SIAM Journal on Computing 18 2 419 427 SIAM algorithms graph parallel http://www.citeulike.org/user/AbnerCYH/article/2588834 <i>SIAM Journal on Discrete Mathematics, Vol. 6, No. 3. (1993), pp. 443-459.</i> An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size Mark Goldberg Thomas Spencer SIAM Journal on Discrete Mathematics, Vol. 6, No. 3. (1993), pp. 443-459. 2008-03-26T09:20:56-00:00 1993 SIAM Journal on Discrete Mathematics 6 3 443 459 SIAM algorithms graph parallel http://www.citeulike.org/user/AbnerCYH/article/2242861 <i>ACM Comput. Surv., Vol. 16, No. 3. (September 1984), pp. 319-348.</i> Parallel graph algorithms Michael Quinn Narsingh Deo doi:10.1145/2514.2515 ACM Comput. Surv., Vol. 16, No. 3. (September 1984), pp. 319-348. 2008-01-17T04:58:39-00:00 1984 ACM Comput. Surv. 0360-0300 16 3 319 348 ACM algorithms parallel