In this work, we utilize dynamic dataflow/data-driven techniques to improve the performance of high performance computing (HPC) systems. The proposed techniques are implemented and evaluated through an efficient, portable, and robust programming framework that enables data-driven concurrency on HPC systems. The proposed framework is based on data-driven multithreading (DDM), a hybrid control-flow/dataflow model that schedules threads based on data availability on sequential processors. The proposed framework was evaluated using several benchmarks, with different characteristics, on two different systems: a 4-node AMD system with a total of 128 cores and a 64-node Intel HPC system with a total of 768 cores. The performance evaluation shows that the proposed framework scales well and tolerates scheduling overheads and memory latencies effectively. We also compare our framework to MPI, DDM-VM, and OmpSs@Cluster. The comparison results show that the proposed framework obtains comparable or better performance.

The exponential growth of sequential processors has come to an end, and thus, parallel processing is probably the only way to achieve performance growth. We propose the development of parallel architectures based on data-driven scheduling. Data-driven scheduling enforces only a partial ordering as dictated by the true data dependencies, which is the minimum synchronization possible. This is very beneficial for parallel processing because it enables it to exploit the maximum possible parallelism. We provide architectural support for data-driven execution for the Data-Driven Multithreading (DDM) model. In the past, DDM has been evaluated mostly in the form of virtual machines. The main contribution of this work is the development of a highly efficient hardware support for data-driven execution and its integration into a multicore system with eight cores on a Virtex-6 FPGA. The DDM semantics make barriers and cache coherence unnecessary, which reduces the synchronization latencies significantly and makes the cache simpler. The performance evaluation has shown that the support for data-driven execution is very efficient with negligible overheads. Our prototype can support very small problem sizes (matrix 16×16) and ultra-lightweight threads (block of 4x4) that achieve speedups close to linear. Such results cannot be achieved by software-based systems.

Thanks to the improvements in semiconductor technologies, extreme-scale systems such as teradevices (i.e., composed by 1000 billion of transistors) will enable systems with 1000+ general purpose cores per chip, probably by 2020. Three major challenges have been identified: programmability, manageable architecture design, and reliability. TERAFLUX is a Future and Emerging Technology (FET) large-scale project funded by the European Union, which addresses such challenges at once by leveraging the dataflow principles. This paper describes the project and provides an overview of the research carried out by the TERAFLUX consortium.

In this paper we present the Data-Driven Multithreading Virtual Machine for the Cell Processor (DDM-VMc). Data-Driven Multithreading is a non-blocking multithreading model that decouples the synchronization from the computation portions of a program allowing them to execute asynchronously in a data-flow manner. The core of the DDM model is the Thread Scheduling Unit (TSU), which schedules threads dynamically at runtime based on data availability. DDM-VMc implements the TSU as a software module running on the PPE core of the Cell, allowing the SPE cores to execute the program threads. DDM-VMc virtualizes the parallel resources of the Cell, handles the heterogeneity of the cores and manages the Cell memory hierarchy efficiently.

The need to exploit multi-core systems for parallel processing has revived the concept of dataflow. In particular, the dataflow multithreading architectures have proven to be good candidates for these systems. In this work we propose an abstraction layer that enables compiling and running a program written for an abstract dataflow multithreading architecture on different implementations. More specifically, we present a set of compiler directives that provide the programmer with the means to express most types of dependencies between code segments. In addition, we present the corresponding toolchain that transforms this code into a form that can be compiled for different implementations of the model. As a case study for this work, we present the usage of the toolchain for the TFlux and DTA architectures.

In this paper we present thread flux (TFlux), a complete system that supports the data-driven multithreading (DDM) model of execution. TFlux virtualizes any details of the underlying system therefore offering the same programming model independently of the architecture. To achieve this goal, TFlux has a runtime support that is built on top of a commodity operating system. Scheduling of threads is performed by the thread synchronization unit (TSU), which can be implemented either as a hardware or a software module. In addition, TFlux includes a preprocessor that, along with a set of simple compiler directives, allows the user to easily develop DDM programs. The preprocessor then automatically produces the TFlux code, which can be compiled using any commodity C compiler, therefore automatically producing code to any ISA. TFlux has been validated on three platforms. A Simics-based multicore system with a TSU hardware module (TFluxHard), a commodity 8-core Intel Core2 QuadCore-based system with a software TSU module (TFluxSoft), and a Cell/BE system with a software TSU module (TFluxCell). The experimental results show that the performance achieved is close to linear speedup, on average 21x for the 27 nodes TFluxHard, and 4.4x on a 6 nodes TFluxSoft and TFluxCell. Most importantly, the observed speedup is stable across the different platforms thus allowing the benefits of DDM to be exploited on different commodity systems.

As in linguistics the semantics co-exist with pragmatics to provide complete and unambiguous meaning to utterances, in the same way the pragmatics should augment the semantics in intelligent applications. Service-oriented computing is an area where such intelligent applications are greatly facilitated. In this paper we propose a pragmatic methodology to Web service discovery which utilizes both the pragmatics and the semantics. This methodology aims to solve a very basic problem of existing semantic discovery approaches: the inability of selecting the most appropriate service among many semantically equivalent Web services.

Query by Browsing (QBB) is a relationally complete paradigm for creating Visual Query Language (VQL)s. It has been adapted successfully for use on handheld devices in the form of the Chiromancer interface, thus placing considerable search capabilities at the fingertips of mobile users. In this paper we describe an enhancement to the QBB paradigm to accommodate continuous queries through the use of active folders, i.e. folders whose contents are constantly updated. We thus demonstrate how such continuous queries coupled with a suitable context-describing database schema can be used to support a variety of context-aware application scenarios. A prototype architecture and context schema are described as are the extensions to the QBB paradigm and the additions to the Chiromancer interface needed to support these scenarios.

This paper describes the data-driven multithreading (DDM) model and how it may be implemented using off-the-shelf microprocessors. Data-driven multithreading is a nonblocking multithreading execution model that tolerates internode latency by scheduling threads for execution based on data availability. Scheduling based on data availability can be used to exploit cache management policies that reduce significantly cache misses. Such policies include firing a thread for execution only if its data is already placed in the cache. We call this cache management policy the CacheFlow policy. The core of the DDM implementation presented is a memory mapped hardware module that is attached directly to the processor's bus. This module is responsible for thread scheduling and is known as the thread synchronization unit (TSU). The evaluation of DDM was performed using simulation of the data-driven network of workstations (D2NOW). D2NOW is a DDM implementation built out of regular workstations augmented with the TSU. The simulation was performed for nine scientific applications, seven of which belong to the SPLASH-2 suite. The results show that DDM can tolerate well both the communication and synchronization latency. Overall, for 16 and 32-node D2NOW machines the speedup observed was 14.4 and 26.0, respectively

In this paper we introduce and formally define Query by Browsing (QBB), a scalable, relationally complete visual query language based on the desktop user interface paradigm and tuple relational calculus that allows the formulation of complex queries over relational, entity-relationship, object-oriented and XML data sources on a variety of handheld and desktop platforms. It is to our knowledge the first visual query language to combine the important characteristics of usability, scalability, expressive power and flexibility. We support these claims by demonstrating the similarity of the QBB paradigm to the popular desktop user interface paradigm, by relating it to relational calculus and relational algebra and by describing Chiromancer II, a Web-based implementation of the QBB paradigm for handheld devices. We also discuss ways in which non-relational sources can be represented and queried and compare QBB to related work in the area of visual query languages for a variety of data models. We finally offer conclusions and thoughts for future work.

Net-dbx-G is a tool that utilizes Java and other World Wide Web tools as an interface to Grid services to help Grid application developers debug their MPI programs from anywhere in the Internet. Net-dbx-G is a source level debugger with the full power of gdb (the GNU Debugger), providing the user with full Grid functionality. The portability of the tool is of great importance as well because it enables the tool to be used on heterogeneous nodes that participate in an MPI enabled, Grid environment. The users of our system simply point their browser to the Net-dbx-G webpage and authenticate to the virtual organization that they are part of. Having at their disposal the shared resources participating with that VO, they start debugging by interacting with the provided GUI environment of the tool. The users can dynamically select which MPI processes to view/debug.

This paper describes Net-dbx, a tool that utilizes Java and other World Wide Web tools for the debugging of MPI programs from anywhere in the Internet. Net-dbx is a source-level interactive debugger with the full power of gdb (the GNU Debugger) augmented with the debug functionality of the public-domain MPI implementation environments. The main effort was on a low overhead, yet powerful, graphical interface supported by low-bandwidth connections. The portability of the tool is of great importance as well because it enables the tool to be used on heterogeneous nodes that participate in an MPI multicomputer. Both needs are satisfied a great deal by the use of WWW browsing tools and the Java programming language. The user of our system simply points his/her browser to the Net-dbx page, logs in to the destination system, and starts debugging by interacting with the tool, just as with any GUI environment. The user can dynamically select which MPI processes to view/debug. A special WWW-based environment has been designed and implemented to host the system prototype.

We discuss and evaluate three optimizations for reducing memory management overhead and data copying costs in SISAL 1.2 programs that build arrays. The first, called framework preconstruction, eliminates superfluous allocate-deallocate sequences in cyclic computations. The second, called aggregate storage subsumption, reduces the management overhead for compound array components. The third, called predictive storage preallocation, eliminates superfluous data copying in filtered array constructions and simplifies their parallelization. We have added all three optimizations to the Optimizing SISAL Compiler with rewarding improvements in SISAL program performance on vector-parallel machines such as those built by Cray Computer Corporation, Convex, and Cray Research.>

Iterative methods for solving linear systems are discussed. Although these methods are inherently highly sequential, it is shown that much parallelism could be exploited in a data-flow system by scheduling the iterative part of the algorithms in blocks and by looking ahead across several iterations. This approach is general and will apply to other iterative and loop-based problems. It is also demonstrated by simulation that relying solely on data-driven scheduling of parallel and unrolled loops results in low resource utilization and poor performance. A graph-level priority scheduling mechanism has been developed that greatly improves resource utilization and yields higher performance.>