Skip to Main Content U.S. Department of Energy
Center for Adaptive Supercomputing - Multithreaded Architectures

Workshop on Irregular Applications: Architectures & Algorithms - IA^3

November 13, 2011
Grand Hyatt Favorita
Seattle, WA, USA

To be held in conjunction with:

SC11

Theme

Many data intensive scientific applications are irregular by nature. They may present irregular data structures, control flow or communication. Current supercomputing systems are organized around components optimized for data locality and regular computation. Developing irregular applications on them demands a substantial effort, and often leads to poor performance. However, solving these applications efficiently will be a key requirement for future systems.

The solutions needed to address their challenges can only come by considering the problem from all the points of view, from micro to system-architectures, from compilers to languages, from libraries to runtimes, up to rethinking how algorithms operate. Only collaborative efforts among researchers with different profiles, including end users, domain experts, and computer scientists, could lead to significant breakthroughs. This workshop aims at bringing together scientists with all these different backgrounds to discuss, define and design methods and technologies for efficiently supporting irregular applications on current and future machines.

Workshop Program

download agenda

9:00 – 9:10 Welcome & introduction
John Feo (Pacific Northwest National Laboratory)
9:10 – 9:50 Keynote 1
“Scalable Algorithms for Massive-scale Graph Analytics”
Fabrizio Petrini (IBM TJ Watson)
9:50 – 10:30 Keynote 2
"Easy and Efficient Graph Analysis with A Domain-Specific Language”
Kunle Olukotun (Stanford University)
10:30 – 11:00 Coffee Break
11:00 – 12:15 Paper Session 1: Algorithms for Irregular Applications
Chair: Simone Secchi (Pacific Northwest National Laboratory)
  1. “An OpenMP Algorithm and Implementation for Clustering Biological Graphs”
     Timothy Chapman (UC Santa Cruz) and Ananth Kalyanaraman (Washington State University)
  2. “Parallel Bipartite Maximum Matching: Worth the Effort?”
    Ariful Azad (Purdue University), Mahantesh Halappanavar (Pacific Northwest   National Laboratory), Florin Dobrian (Conviva Inc.), and Alex Pothen (Purdue University)
  3. “Parallel Simulation of Dendritic Growth On Unstructured Grids”
    Andreas Schäfer (Friedrich-Alexander-Universität Erlangen-Nürnberg), Julian Hammer (Friedrich-Alexander-Universität Erlangen-Nürnberg), Dietmar Fey (Friedrich-Alexander-Universität Erlangen-Nürnberg)
12:15 – 13:45 Lunch Break
13:45 – 15:00 Paper Session 2: Architectures for Irregular Applications
Chair: Antonino Tumeo (Pacific Northwest National Laboratory)
  1. “Implementation of a Hierarchical N-Body Simulator using the OmpSs Programming Model”
    Miquel Pericàs (Barcelona Supercomputing Center), Yoav Etsion (Barcelona Supercomputing Center), Xavier Martorell (Barcelona Supercomputing Center)
  2. “Exploring Irregular Memory Accesses on FPGAs.”
    Robert Halstead (UC Riverside), Jason Villarreal (Jacquard Computing) and Walid Najjar (UC Riverside)
  3. “A Memory Accelerator with Gather Functions for Bandwidth-bound Irregular Applications”
    Noboru Tanabe (Toshiba), Boonyasitpichai Nuttapon (Tokyo University of Agriculture and Technology), Hironori Nakajo (Tokyo University of Agriculture and Technology), Yuka Ogawa (Nara Women's University), Junko Kogou (Nara Women's University), Masami Takata (Nara Women's University) and Kazuki Joe (Nara Women's University)
15:00 – 15:30 Coffee Break
15:30 – 17:00 Panel Session
Moderator: Oreste Villa (Pacific Northwest National Laboratory)

Panelists: David A. Bader (Georgia Tech), Walid Najjar (UC Riverside), Alex Pothen (Purdue University), Michael Garland (NVIDIA), Udeepta Bordoloi (AMD), Fabrizio Petrini (IBM TJ Watson), Kunle Olukotun (Stanford University)

Call for Papers

Irregular applications are a broad class of applications with unpredictable memory access patterns, control structures, and/or network transfers. They typically use pointer-based data structures such as graphs and trees, often present fine-grained synchronization and communication, and generally operate on very large data sets. They have a significant degree of latent parallelism, which however is difficult to exploit due to their complex behavior. Current high performance architectures rely on data locality and regular computation to tolerate access latencies, and often do not cope well with the requirements of these applications. Furthermore, irregular applications are difficult to scale on current supercomputing machines, due to their limits in fine-grained synchronization and small data transfers.

Irregular applications pertain both to well established and emerging fields, such as Computer Aided Design (CAD), bioinformatics, semantic graph databases, social network analysis, security. Addressing the issues of these applications on current and future architectures will become critical to solve the scientific challenges of the next few years. This workshop seeks to explore solutions for supporting efficient execution of irregular applications in the form of new features at the level of the micro- and system-architecture, network, languages and libraries, runtimes, compilers, analysis, algorithms. Topics of interest, of both theoretical and practical significance, include but are not limited to:

  • Micro- and System-architectures
  • Network and memory architectures
  • Heterogeneous and custom architectures (GPUs, FPGAs)
  • Modeling and evaluation of architectures
  • Innovative algorithms
  • Parallelization techniques and data structures
  • Languages and programming models
  • Library and runtime support
  • Compiler and analysis techniques

Besides regular papers, papers describing work in progress or incomplete but sound new innovative ideas related to the workshop theme are also encouraged. We solicit both 8-page regular papers and 4-page position papers.

Authors of selected papers from the workshop will be invited to submit an extended version of their manuscript to the Special Issue on: "Architectures and Algorithms for Irregular Applications" of the International Journal of High Performance Computing and Networking.

Paper Submission Guidelines

Authors should submit an abstract by Thursday, 15 September 2011 (11:59 PM PDT - EXTENDED). They should submit the full version of the paper by Thursday, 15 September 2011 (11:59 PM PDT - EXTENDED). All submissions should be in double-column, single-spaced letter format, using 10-point size fonts, with at least 1 inch margins on each side. Submitted manuscripts may not exceed 8 pages in length for regular papers and 4 pages for position papers including figures, tables and references.

To submit a paper, please go to EasyChair and follow the instructions.

Important Dates

  • 15 September 2011 (11:59 PM PDT - EXTENDED): Abstract submission
  • 15 September 2011 (11:59 PM PDT - EXTENDED): Full paper or extended abstract submission
  • 10 October 2011: Notification of acceptance
  • 24 October 2011: Camera-ready due
  • 13 November 2011: Workshop

Organizers

Program Committee

  • David A. Bader, Georgia Tech
  • Udeepta Bordoloi, AMD
  • Bryan Catanzaro, NVIDIA
  • Daniel Chavarria, Pacific Northwest National Laboratory
  • Roberto Gioiosa, Barcelona Supercomputing Center
  • Matteo Monchiero, Intel
  • Walid Najjar, University of California Riverside
  • Gianluca Palermo, Politecnico di Milano
  • Cristina Silvano, Politecnico di Milano
  • Pedro Trancoso, University of Cyprus

CASS-MT

Research and Development

Resources