In supercomputing systems, architectural changes that increase computational power are often reflected in the programming model. As a result, in order to realize and sustain the potential performance of such systems, it is necessary in practice to deal with architectural details and explicitly manage the resources to an increasing extent. In particular, programmers are required to develop code that exposes a high degree of parallelism, exhibits high locality, dynamically adapts to the available resources, and hides communication latency. Hiding communication latency is crucial to realize the potential of today's distributed memory machines with highly parallel processing modules, and technological trends indicate that communication latencies will continue to be an issue as the performance gap between computation and communication widens. However, under Bulk Synchronous Parallel models, the predominant paradigm in scientific computing, scheduling is embedded into the application code. All the phases of a computation are defined and laid out as a linear sequence of operations limiting overlap and the program's ability to adapt to communication delays. This thesis proposes an alternative model, called Tarragon, to overcome the limitations of Bulk Synchronous Parallelism. Tarragon, which is based on dataflow, targets latency tolerant scientific computations. Tarragon supports a task-dependency graph abstraction in which tasks, the basic unit of computation, are organized as a graph according to their data dependencies, i.e. task precedence. In addition to the task graph, Tarragon supports metadata abstractions, annotations to the task graph, to express locality information and scheduling policies to improve performance. Tarragon's functionality and underlying programming methodology are demonstrated on three classes of computations used in scientific domains: structured grids, sparse linear algebra, and dynamic programming. In the application studies, Tarragon implementations achieve high performance, in many cases exceeding the performance of equivalent latency-tolerant, hard coded MPI implementations. The results presented in this dissertation demonstrate that data-driven execution, coupled with metadata abstractions, effectively support latency tolerance. In addition, performance metadata enable performance optimization techniques that are decoupled from the algorithmic formulation and the control flow of the application code. By expressing the structure of the computation and its characteristics with metadata, the programmer can focus on the application and rely on Tarragon and its run-time system to automatically overlap communication with computation and optimize the performance

Accurate and continuous monitoring and profiling are important issues of performance tuning and scheduling optimization. In desktop grid systems based on sandboxing techniques these issues are particularly challenging because (1) subjobs inside sandboxes are executed in a virtual environment and (2) sandboxes are usually reset to an initial (empty) state at each subjob termination. To address this problem, we present in this paper DGMonitor, a monitoring tool to build a global, accurate and continuous view of real resource utilization for desktop grids based on sandboxing techniques. Our monitoring tool provides unobtrusive and reliable performance measures, uses a simple performance data model and is easy to use. Our work demonstrates that DGMonitor can easily take over the monitoring of large desktop grids (up to 12000 workers) maintaining low load in terms of resource consumption due to the monitoring process (less than 0.1%) on desktop PCs. Although we use DGMonitor with the Entropia DGrid platform, it can be easily integrated in other desktop grids and its data can be used as an information source for existing information services for performance tuning and scheduling optimization. Keywords: Performance monitoring and profiling, desktop grids, sandboxing techniques, distributed computing.

Pre-2018 CSE ID: CS2003-0770

Memcomputing is a novel computing paradigm that employs time non-local dynamical systems to compute with and in memory. The digital version of these machines [digital memcomputing machines or (DMMs)] is scalable, and is particularly suited to solve combinatorial optimization problems. One of its possible realizations is by means of standard electronic circuits, with and without memory. Since these elements are non-quantum, they can be described by ordinary differential equations. Therefore, the circuit representation of DMMs can also be simulated efficiently on our traditional computers. We have indeed previously shown that these simulations only require time and memory resources that scale linearly with the problem size when applied to finding a good approximation to the optimum of hard instances of the maximum-satisfiability problem. The state-of-the-art algorithms, instead, require exponential resources for the same instances. However, in that work, we did not push the simulations to the limit of the processor used. Since linear scalability at smaller problem sizes cannot guarantee linear scalability at much larger sizes, we have extended these results in a stress-test up to 64×10⁶ variables (corresponding to about 1 billion literals), namely the largest case that we could fit on a single core of an Intel Xeon E5-2860 with 128 GB of dynamic random-access memory (DRAM). For this test, we have employed a commercial simulator, Falcon of MemComputing, Inc. We find that the simulations of DMMs still scale linearly in both time and memory up to these very large problem sizes versus the exponential requirements of the state-of-the-art solvers. These results further reinforce the advantages of the physics-based memcomputing approach compared with traditional ones.

Hiding communication behind useful computation is an important performance programming technique but remains an inscrutable programming exercise even for the expert. We present Bamboo, a code transformation framework that can realize communication overlap in applications written in MPI without the need to intrusively modify the source code. We reformulate MPI source into a task dependency graph representation, which partially orders the tasks, enabling the program to execute in a data-driven fashion under the control of an external runtime system. Experimental results demonstrate that Bamboo significantly reduces communication delays while requiring only modest amounts of programmer annotation for a variety of applications and platforms, including those employing co-processors and accelerators. Moreover, Bamboo's performance meets or exceeds that of labor-intensive hand coding. The translator is more than a means of hiding communication costs automatically; it demonstrates the utility of semantic level optimization against a well-known library.