Irregular applications occur in many subject matters. They pertain both to well established and emerging fields, such as Computer Aided Design (CAD), bioinformatics, semantic graph databases, machine learning, analysis of social, transportation, communication and other types of networks, and computer security.
Irregular applications are inherently parallel, but present unpredictable memory access patterns, control structures, and/or network transfers. They typically operate on large sets of data organized in pointer or linked lists-based structures (such as graphs, sparse matrices, unbalanced trees, unstructured grids), which are difficult to partition on distributed memory systems in a balanced way. They often present fine-grained synchronization and communication.
Current high-performance architectures rely on data locality, regular computations, structured data and easily partitionable datasets. Scaling them on parallel systems is even harder, because current limits with fine-grained, unpredictable transactions, and synchronization. Current frameworks and infrastructure that deal with kernels and algorithms that exhibits irregular behaviors are limited in performance and scalability by their execution engines (hardware or softwares). Additionally, while there is an increased need for solutions able to simultaneously deal with regular and irregular workloads with similar efficiency (for example, attributed graphs where graph views co-exists with table views, workflows where combinatorial or graph methods provide pre-processing of data or more computational efficient approaches to solve scientific simulations, workflows integrating machine learning approaches with graph methods), existing systems are unable to provide such integration.
Addressing the issues of irregular applications on current and future system architectures, and enabling efficient integration of regular and irregular workloads, will become critical to solve the scientific challenges of the next few years.
This special issue 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, including multi- and many-core designs, heterogeneous processors, accelerators (GPUs, vector processors, Automata processor), reconfigurable (coarse grained reconfigurable and FPGA designs) and custom processors
• Network architectures and interconnect (including high-radix networks, optical interconnects)
• Novel memory architectures and designs (including processors-in memory)
• Impact of new computing paradigms on irregular workloads (including neuromorphic processors and quantum computing)
• Modeling, simulation and evaluation of novel architectures with irregular workloads
• Innovative algorithmic techniques
• Combinatorial algorithms (graph algorithms, sparse linear algebra, etc.)
• Impact of irregularity on machine learning approaches
• Parallelization techniques and data structures for irregular workloads
• Data structures combining regular and irregular computations (e.g., attributed graphs)
• Workflows combining regular and irregular workloads
• Approaches for managing massive unstructured datasets (including streaming data)
• Languages and programming models for irregular workloads
• Library and runtime support for irregular workloads
• Compiler and analysis techniques for irregular workloads
• High performance data analytics applications, including graph databases
• Hardware and software data analytics infrastructures that integrates graph algorithms and machine learning
This special issue solicits, in particular, papers discussing approaches that span multiple level of the stack, ideally providing application specific, end-to-end solutions. Papers should identify their contributions with respect to existing solutions. Only technical articles describing previously unpublished, original, state-of-the-art research and not currently under review by a conference or a journal will be considered. Works based on previously published research should provide substantiation new content and clearly identify the novel contribution with respect to previous works.