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

IA3 Workshop on Irregular Applications: Architectures & Algorithms

Sunday, November 17, 2013
Colorado Convention Center
Denver, Colorado USA

To be held in conjunction with:

To be held in cooperation with:



Many data intensive scientific applications are by nature irregular. They may present irregular data structures, irregular control flow or irregular 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, executing irregular applications efficiently will be a key requirement for future systems.

The solutions needed to address irregular applications challenges can only come by considering the problem from all perspectives: from micro- to system-architectures, from compilers to languages, from libraries to runtimes, from algorithm design to data characteristics. Only collaborative efforts among researchers with different expertise, 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 systems.

Workshop Program

View the entire program, with abstracts.

Time: 9:00 - 10:00
Paper Session 1: Software Approaches for Irregular Applications
Chair: Vito Giovanni Catellana (Politecnico di Milano and PNNL)

In-Memory Data Compression for Sparse MatricesOrion Lawlor (U. Alaska Fairbanks)
A Synthetic Task Model for HPC-Grade Optical Network Performance EvaluationSébastien Rumley (Columbia University), Lisa Pinals (Columbia University), Gilbert Hendry (Sandia National Laboratories) and Keren Bergman (Columbia University)
An AMR Computation and Communication Dependency and Analysis Methodology (Short presentation)Cy Chan (Lawrence Berkeley National Laboratory), Joseph Kenny (Sandia National Laboratories), Gilbert Hendry (Sandia National Laboratories), Vincent Beckner (Lawrence Berkeley National Laboratory), John Bell (Lawrence Berkeley National Laboratory) and John Shalf (Lawrence Berkeley National Laboratory)

Time: 10:30 - 12:00
Paper Session 2: Accelerators for Irregular Applications
Chair: Silvia Lovergine (Politecnico di Milano and PNNL)

A Novel Finite Element Method Assembler for Co-processors and AcceleratorsNina Hanzlikova (Dublin City University) and Eduardo Rocha Rodrigues (IBM Research)
The Energy Case for Graph Processing on Hybrid CPU and GPU SystemsAbdullah Gharaibeh (The University of British Columbia), Elizeu Santos-Neto (The University of British Columbia), Lauro Beltr√£o Costa (The University of British Columbia) and Matei Ripeanu (The University of British Columbia)
Register Level Sort Algorithm on Multi-Core SIMD Processors (Short presentation)Xiaochen Tian (The University of Tokyo), Kamil Rocki (The University of Tokyo) and Reiji Suda (The University of Tokyo)
Nonzero Pattern Analysis and Memory Access Optimization in GPU-based Sparse LU Factorization for Circuit Simulation (Short presentation)Xiaoming Chen (Tsinghua University), Du Su (Tsinghua University), Yu Wang (Tsinghua University) and Huazhong Yang (Tsinghua University)
On the GPU performance of cell-centered finite volume method over unstructured tetrahedral meshes (Short presentation)Johannes Langguth (Simula Research Laboratory), Nan Wu (Simula Research Laboratory and National University of Defense Technology), Jun Chai (Simula Research Laboratory and National University of Defense Technology) and Xing Cai (Simula Research Laboratory and University of Oslo)
Parallel Implementations of Ensemble Data Assimilation for Atmospheric Prediction (Short presentation)Jeffrey Anderson (National Center for Atmospheric Research), Helen Kershaw (National Center for Atmospheric Research) and Nancy Collins (National Center for Atmospheric Research)

Time: 1:30 - 2:30
Paper Session 3:Energy and Performance of Irregular Applications on homogeneous architectures
Chair: Alessandro Morari (PNNL)

Maximizing the performance of irregular applications on multithreaded, NUMAGuojing Cong (IBM TJ Watson Research Center), Huifang Wen (IBM TJ Watson Research Center)
Analysis of Computing and Energy Performance of Multicore, NUMA, and Manycore Platforms for an Irregular ApplicationMárcio Castro (Federal University of Rio Grande do Sul), Emilio Francesquini (University of Sao Paulo), Thomas Messi Nguélé (University of Yaoundé 1) and Jean-François Mehaut (Laboratoire LIG)
Parallel Sparse FFT (Short presentation)Cheng Wang (University of Houston), Mauricio Araya-Polo (Shell International E&P Inc.), Sunita Chandrasekaran (University of Houston), Amik St-Cyr (Shell International E&P Inc.), Barbara Chapman (University of Houston) and Detlef Hohl (Shell International E&P Inc.)

Time: 2:30 - 3:00
Keynote 1: Non-Obvious Relationship Analysis: An Irregular Challenge Problem, Jay Brockman, University of Notre Dame
Chair:John Feo (PNNL)

Time: 3:30 - 4:00
Keynote 2: Asynchronous Runtime Systems for Irregular Applications, Vivek Sarkar, Rice University
Chair:Oreste Villa (NVIDIA)

Time: 4:00 - 5:30
Panel:High Performance Irregular Applications: where are we headed?
Moderator: Antonino Tumeo (PNNL)

Panel Members
Tor Aamodt, University of British Columbia; Jay Brockman, University of Notre Dame; Andrew Lenharth, The University of Texas, Austin; Richard Murphy, Micron; Bill Brantley, AMD; Vivek Sarkar, Rice University

Call for Papers

A broad class of applications is irregular. Irregular applications present unpredictable memory access patterns, control structures, and/or network transfers. They typically use pointer or linked lists-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 is however difficult to fully exploit because of their complex behavior. Beside performance, another significant concern for emerging irregular applications is the size of the datasets. In fact, modern applications operate on massive amount of data, often unstructured, which are very difficult to partition and easily generate load unbalance.

Current high performance architectures rely on data locality, regular computations, structured data and easily partitionable datasets. They do not cope well with the requirements of these applications. Furthermore, irregular applications are difficult to scale on current supercomputing machines, because of their limits with fine-grained communication and synchronization. Irregular applications pertain both to well established and emerging fields, such as Computer Aided Design (CAD), bioinformatics, semantic graph databases, social network analysis, and computer 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 design, development and 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
  • Manycore, heterogeneous and custom architectures (Tilera, GPUs, FPGAs)
  • Modeling and evaluation of architectures
  • Innovative algorithmic techniques
  • Parallelization techniques and data structures
  • Languages and programming models
  • Library and runtime support
  • Compiler and analysis techniques
  • Case studies of irregular applications (e.g. Semantic Graph Databases, Data Mining, Security, Bioinformatics)

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.

Important Dates

  • Abstract Submission: 2 September 2013 (23:59 PST)
  • Paper Submission: 9 September 2013 (23:59 PST)
  • Notification of Acceptance: 9 October 2013
  • Workshop: 17 November 2013

Paper Submission Guidelines

Submission site:

All submissions should be in double-column, single-spaced letter format, using 10-point size fonts, with at least one inch margins on each side. Submitted manuscripts may not exceed eight pages in length for regular papers and four pages for position papers including figures, tables and references. For any question, please contact the organizers.

Workshop Chairs

Publicity Chair

  • Alessandro Morari, UPC and Pacific Northwest National Laboratory

Submission Chair

  • Silvia Lovergine, Politecnico di Milano and Pacific Northwest National Laboratory

Publication Chair

  • Vito Giovanni Castellana, Politecnico di Milano and Pacific Northwest National Laboratory

Program Committee

    • Keren Bergman, Columbia University, USA
    • David Brooks, Harvard University, USA
    • Bryan Catanzaro, NVIDIA, USA
    • Selim Ciraci, Pacific Northwest National Laboratory, USA
    • Georgi Gaydadjiev, Chalmers University, Sweden
    • Mahantesh Halappanavar, Pacific Northwest National Laboratory, USA
    • John Leidel, Cray, USA
    • Kamesh Madduri, The Pennsylvania State University, USA
    • Joseph Manzano, Pacific Northwest National Laboratory, USA
    • Matteo Monchiero, Intel, USA
    • Walid Najjar, University of California, Riverside, USA
    • Gianluca Palermo, Politecnico di Milano, Italy
    • Fabrizio Petrini, IBM TJ Watson, USA
    • Keshav Pingali, University of Texas, Austin, USA
    • John Shalf, Lawrence Berkeley National Laboratory, USA
    • Pedro Trancoso, University of Cyprus, Cyprus
    • Mateo Valero, Barcelona Supercomputing Center, Spain


Research and Development