Lab Home | Phone | Search
	Center for Nonlinear Studies
	Home  ▶ People   Current   Affiliates   Alumni   Visitors   Students  ▶ Research   ICAM-LANL  ▶ Publications   2007   2006   2005   2004   2003   2002   2001   2000   <1999  ▶ Conferences   Workshops   Sponsorship  ▶ Talks   Colloquia   Seminars   Quantum Lunch   Archive   Kac Lectures   Dist. Quant. Lecture   Ulam Scholar   Colloquia     Jobs  ▶ Students   Summer Research   Graduate Positions  ▶ Visitors   Description  ▶ Services   General   PD Travel Request     History of CNLS     Maps, Directions   CNLS Office   T-Division   LANL				Monday, December 17, 201210:00 AM - 11:00 AMCNLS Conference Room (TA-3, Bldg 1690) Seminar Hash-based Algorithms for Massively Parallel Architectures Bob Robey and Jonathan RobeyEulerian Applications Group, XCP-2 and We have developed a set of hash-based algorithms with a base operational complexity of O(n) which can replace the typically tree-based O(n log n) algorithms. These hash-based algorithms are also suitable for the finer grain parallelism of the next generation of parallel computing. To take full advantage of this new algorithm, a whole class of mesh-based operations (or in more general terms, discretized data) including sorting, neighbor calculations, remapping and table look-ups are demonstrated. Speed-ups on the CPU over current algorithms can be as high as 50x. These algorithms are also much easier to implement on the GPU and other future architectures than current tree-based algorithms with additional speed-ups of 10x-50x. Host: Mikhail Shashkov, XCP-4 Methods and Algorithms, 667-4400