Heterogeneous processors, consisting of CPU cores and an integrated GPU on the same die, are currently the standard in desktop and mobile platforms. The number of CPU cores is increased with every new generation, and integrated GPUs are constantly being improved in performance and energy efficiency. This raises the importance of developing programming methods and techniques to benefit general purpose applications on heterogeneous processors as more parallelism can be achieved. This dissertation addresses this challenge by studying new ways of exploiting parallelism on CPU cores as well as the integrated GPU, focusing on blocking and non-blocking data structures.

A new thread synchronization mechanism for parallel geometric algorithms dubbed Spatial Locks is first introduced. This synchronization mechanism ensures thread synchronization on geometric algorithms that perform concurrent operations on geometric surfaces in two- or three-dimensional spaces. A parallel algorithm for mesh simplification is chosen to illustrate the Spatial Locks usefulness when parallelizing geometric algorithms with ease on multi-core machines. Experimental results show the advantage of using this synchronization mechanism where significant computational improvement can be achieved compared to alternative approaches.

Non-blocking data structures are commonly used by many multi-threaded applications, and their implementation is based on the use of atomic operations. New computing architectures, such as Intel CPU/iGPU processors, have incorporated data-parallel processing through SIMD instructions, including in some cases support for atomic SIMD instructions and SIMT processing on the integrated GPU. A new framework called \textit{SIMD-node Transformations} to implement non-blocking data structures using multi-threaded and SIMD processing is proposed. As a result, it is shown that one- and multi-dimensional data structures, such as skiplists, k-ary trees and multi-level lists, can embrace SIMD processing through these transformations. Finally, important performance gains obtained when applying these transformations to concrete data structures are reported.

Solution of lnitial Value Problems (IVPs) is an important application in scientific computing. Methods for solving these problems use techniques for reducing the error and increasing the speed of the computation. This paper introduces a class of algorithms which dynamically reconfigure their operating parameters to reduce the computation time. By dynamically varying the precision of the arithmetic being performed, it is possible to obtain dramatic speedups on certain architectures when solving IVPs. This paper illustrates how various architectures impact on a dynamic precision version of the Runge-Kutta-Fehlberg algorithm. It is shown that a speedup of over 30 percent is possible for both massively parallel processors and vector supercomputers.

Least Common Ancestor Networks (LCANs) comprise levels of switches that enable communication in two directions. LCANs are a generalization of previously developed networks including fat-trees, baseline networks, SW-banyans and the router networks of the TRAC and the CM-5. In this paper, LCANs are characterized and the routing capabilities of important subclasses are analyzed.

Improvements in performance and energy efficiency often require deep understanding of the complex interactions between hardware and software components. Hardware performance events provide low-level insights about the behavior of a program in real hardware while imposing negligible overhead. Such low overhead allows real-time profile in production environments and makes them useful tools for Feedback Directed Optimization, Software and Hardware Validation, Security, and Performance Analysis among many other applications.

When performance counters are sampled, the perturbation imposed on the monitored task increases with the sampling frequency; restricting the maximum number of sample points that can be acquired in a single run to a few hundreds of sample points per second of execution. This limited sampling frequency, together with the non-deterministic nature of many performance events and the systematic and random errors in the number of measured events caused by bugs and design limitations, had restricted the utilization of performance events in applications that require fine granularity and precision. The error and non-determinism of performance events makes imperative to develop solid methodologies to analyze the data collected from performance counters.

This dissertation presents what we believe is the first formal treatment of methodologies aimed to increase the precision of estimates of performance events in two scenarios: (1) The first scenario is estimation of a trend performance trace; the problem of estimating the cumulative number of performance events that have occurred at each moment during the execution of a task. We propose the utilization of a regression model that combines sample points from different executions and enforces monotonicity constraints in order to increase precision and granularity of the estimator. Additionally, we compare multiple approaches to interpolation of unobserved points in the trace. We present experimental verification of the superiority of the proposed methodology. (2) The second scenario is the attribution of performance events to dynamic instructions. We propose a methodology to build a regression model that associates performance events with dynamic instructions, rather than static ones, allowing to separately estimate performance events for different instances of the same static instructions, ie. first iteration of a loop versus others. We demonstrate that the presented methodology provide more accurate estimates than the traditional approach, while requiring much less sample points.

Finally, we study the structure of the regression problems created in each scenario and show two particular cases that can be solved in linear time and space, either by mapping the problem into a total order Isotonic Regression problem, solvable in linear time with the well-known Pool of Adjacent Violators algorithm, or using a new dynamic algorithm, linear time algorithm proposed in this dissertation. In both cases, the linear time complexity is a significant improvement over the traditional Non-negative Least Squares, Linear or Quadratic Programming utilized to solve the general case.

In a general-purpose multicore parallel multithreaded environment, multiple threads work simultaneously to finish a task faster. Usually, threads need to communicate with each other due to the need to share data or synchronize access to shared data. Communications commonly occur when threads need to wait for the computational results of other threads before continuing their own computations; all necessary data dependencies need to be met before subsequent computations take place.

A barrier is a synchronization construct that enforces a collective pause and data sharing at a given execution point between all participating threads of a parallel computation. No thread proceeds beyond a barrier until all other threads have reached it. However, in a general-purpose system where many processes compete for the available computational cores, a scheduler decides which thread gets a core to execute its next line of code. The barrier can easily become a performance bottleneck due to its global blocking nature; one preempted thread blocks the progress of all other threads that are waiting at a barrier.

This dissertation introduces a novel technique that changes the global nature of the barrier into a distributed data-driven synchronization model with non-blocking thread progression guarantees. The idea is to exploit the algorithm-based memory access patterns to extract peer-to-peer interthread communication and remove the explicit use of a barrier synchronization construct. Our proposed technique is experimentally validated. The results are promising and show considerable robustness in performance as opposed to their barrier-based algorithm counterparts.

Orthogonal graphs were introduced as a simple but powerful tool for the description and analysis of a class of interconnection networks. Routing, and hence finding shortest paths between any two nodes of an orthogonal graph, becomes an important problem. It is shown in this paper that routing in this class of graphs reduces to a node covering problem in the bipartite coverage graph of the orthogonal graph. A minimum cover clearly leads to a shortest path. In general, the problem of finding the mínimum node cover in a bipartite graph is NP-complete. However, the bipartite coverage graphs corresponding to orthogonal graphs have a regular pattern of edges. This allows the development of a routing algorithm which results in a minimum cover. The procedure executes in polynomial time in the number of bit-nodes of the bipartite graph. It therefore results in a shortest path algorithm whose time complexity is quadratic in the logarithm of the number of nodes in the original orthogonal graph.

In this paper we analyze a generalization of the traditional delta network, introduced by Patel [21], and dubbed Expanded Delta Network (EDN). These networks provide in general multiple paths that can be exploited to reduce contention in the network resulting in increased performance. The crossbar and traditional delta networks are limiting cases of this class of networks. However, the delta network does not provide the multiple paths that the more general expanded delta networks provide, and crossbars are to costly to use for large networks. The EDNs are analyzed with respect to their routing capabilities in the MIMD and SIMD models of computation.

The concepts of capacity and clustering are also addressed. In massively parallel SIMD computers, it is the trend to put a larger number processors on a chip, but due to I/O constraints only a subset of the total number of processors may have access to the network. This is introduced as a Restricted Access Expanded Delta Network of which the MasPar MP-1 router network is an example.

Multistage interconnection networks (MIN's) allow communication between terminals on opposing sides of a network. Lowest Common Ancestor Networks (LCAN's) [1] have switches capable of connecting bi-directional links in a permutation pattern that additionally permits communication between terminals on the same side. Self-routing LCAN's have interesting permutation routing capabilities and are highly partionable. This paper characterizes self-routing LCAN's and analyzes their permutation routing capabilities. It is shown that the routing network of the CM-5 is a particular instance of an LCAN.

This paper addresses the problem of providing a parallel virtual memory system with an efficient swap file structure. It thas been observed, experimentally, that the way data is organized in a parallel I/O environment greatly influences the I/O performance [9,6]. Thereforem if virtual memory is to be implemented in parallel machienes, its disk swap space organization will be one of the key factors determining the virtual memory stystem's efficiency.We analyze different parallel file organiations in order to determine which one better suits the needs of a parallel virtual memory system.

Simulation results collected thus far indicate that the best strategy is to assign to each I/O node data that will be utilized mostly by neighbor processors. We observed that this approach better load balances I/O requests among I/O nodes and better explores inter-processor locality.

Lowest Common Ancestor (LCA) networks are built using switches capable of connecting u + d inputs/outputs in a permutation pattern. For n source nodes and I stages of switches, n/d switches are used in stage l - n/d - u/d in stage l - 2, and in general , n-u^l-i-l/d^l-i switches in stage i. The resulting hierarchical structure possesses interesting connectivity and permutational properties. A full characterization of LCA networks is presented together with a permutation routing algorithm for a family of LCA networks. The algorithm uses the network itself to collect and disseminate information about the permutation. A schedule of O(dp log_d/u n) passes is obtained with a switch set-up cost factor of O(log_d/u n) (p is the minimum number of passes that an algorithm with global knowledge schedules).