Research on mental model representations developed by programmers during parallel program comprehension is important for informing and advancing teaching methods including model based learning and visualizations. However, there is a significant lack of empirical research on mental models formed during the comprehension of parallel programs. We present an empirical method for externalizing and mapping mental models of learners and its novel application to a programming context. Participants externalize their mental models by drawing diagrams to depict the execution of a parallel program during a code tracing task. The code tracing task is performed prior to and during instruction on parallel programming in C using OpenMP. The progression of the mental models is analyzed using a rubric to determine how they developed and changed as participants learned. This poster presents our work in progress and preliminary results.

Summary In this paper, we develop a multi‐granularity locking scheme for Java PackedObjects, an experimental enhancement introduced in IBM's J9 Java Virtual Machine. The packed object model organizes data in a multi‐tier manner in which object data can be nested in the container object instead of being pointed to by an object reference, as in the traditional Java object model. This new object data model creates new challenges for multi‐tier data synchronization, requiring concurrent locks on the multi‐tier data of different granularities for maintaining consistency. This is different from the traditional Java synchronization model. In this paper we make use of a concurrent multiway tree to represent the containing and ordering relationship between PackedObjects at different tiers and develop an efficient multi‐granularity locking scheme allowing multiple threads to concurrently manipulate the concurrent multiway tree for synchronization operations. In the evaluation, we compare our new tree‐based multitierSync with the previous multitierSync approaches based on linked‐lists (optimized‐list‐based and lazy‐list‐based). The experimental results show that the tree‐based MultitierPackedSync outperforms the list‐based approaches considerably in different workloads, and the higher the workload, the better the performance gains achieved by the tree‐based MultitierPackedSync.

In a shared cluster facility scheduling of parallel jobs is an important factor that can affect the performance and turnaround time of the submitted jobs. To solve hard tree search problems, we have designed the Dynamic Moldable Tree Search (DMTS) framework. The DMTS framework allows existing serial tree search applications to run in parallel with very little development effort. The DMTS framework is designed to run on parallel computing infrastructures, including clusters, computational grids, and clouds. Target applications for the DMTS framework are hard tree search problems such as Boolean satisfiability (SAT) problems. SAT is amongst the most important problems in theoretical computer science. In this paper we present a parallel Dynamic Moldable SAT (DMSAT) solver. DMSAT runs on top of the DMTS framework. DMSAT is a parallel version of minis at, miniSat is one of the most widely used open source SAT solvers. We compare the performance of DMSAT with PMSAT and miniSat. Our experimental results show that the dynamic moldable model of DMSAT perform much better than the other SAT solvers. In SAT race competitions all those problems that are not solved by a SAT solver within 1200 seconds are marked as unsolvable. DMSAT is also able to solve hard SAT problems that were not solvable by miniSat in the past SAT races.

As transistor density grows, increasingly complex hardware designs are implemented. In order to manage this complexity, hardware design can be performed at a higher level of abstraction. High level synthesis enables the automatic conversion of algorithms into hardware implementations, abstracting away the underlying complexities of hardware from the designer. A number of high level synthesis tools have recently been developed, including an OpenMP to Handel-C translator. Improvements to the translator, including a new compiler directive allowing customizable register width, are described. Using a set of benchmark tests, the OpenMP to Handel-C translator is evaluated on several criteria, with the goal of evaluating the variable bit-width effects and identifying further areas for improvement.

Heterogeneous distributed computing is found in a variety of fields including scientific computing, Internet and mobile devices. Computational grids focusing primarily on computationally-intensive operations have emerged as a new infrastructure for high performance computing. Specific algorithms such as scheduling, load balancing and data redistribution have been devised to overcome the limitations of these systems and take full advantage of their processing power. However, experimental validation and fine-tuning of such algorithms require multiple heterogeneous platforms and configurations. We present EHGRID, a computational grid emulator based on the heterogeneous emulator Wrekavoc. EHGRID reshapes the virtual topology of a homogeneous cluster, degrades the performance of the processors and modifies the characteristics of the network links in an accurate, independent and reproducible way. We demonstrate its utility using two parallel matrix-vector programs and selected NAS parallel benchmarks on a series of four emulated grids.

In this paper we describe the parallelization of a dynamic programming algorithm used to find common RNA secondary structures including pseudoknots and similar structures. The sequential algorithm is recursive and uses memoization and data-driven selective allocation of the tables, in order to cope with the high space and time demands. These features, in addition to the irregular nature of the data access pattern, present particular challenges to parallelization. We present a new manager-worker approach, where workers are responsible for task creation and the manager's sole responsibility is overseeing load balancing. Special considerations are given to the management of distributed, dynamic task creation and data structures, along with general inter-process communication and load balancing on a heterogeneous computational platform. Experimental results show a modest level of speedup with a highly-scalable level of memory usage, allowing the comparison of much longer RNA molecules than is possible in the sequential implementation.

A number of graph partitioners are currently available for solving linear systems on parallel computers. Partitioning algorithms divide the graph that arises from the linear system into a specified number of partitions such that the workload per processor is balanced and the communication between the processors is minimized. The measure of partition quality is often taken to be the number of edges cut by the partition. Ultimately the quality of a partition will be reflected in the execution time of the parallel application. In this paper, we introduce a linear solver benchmark that enables comparison of partition quality. This work also serves to motivate further work on developing benchmarks for graph partitioners.

Network intrusion detection systems (NIDS) and quality of service (QoS) demands have been steadily increasing over the past few years. Current solutions using software become inefficient running on high speed high volume networks and will end up dropping packets. Hardware solutions are available and result in much higher efficiency but present problems such as flexibility and cost. Our proposed system uses a modified version of Snort, a robust widely deployed open-sourced NIDS. It has been found that Snort spends at least 30%-60% of its processing time doing pattern matching. Our proposed system runs Snort in software until it gets to the pattern matching function and then offloads that processing to the field programmable gate array (FPGA). The software can then go on to other processing while it waits for the results from the FPGA. The hardware is able to process data at upto 1.7 GB/s on one Xilinx XC2VP100 FPGA. The design is scaleable and will allow for multiple FPGAs to be used in parallel to increase the processing speed even further.

Parallel applications based on irregular meshes make use of mesh partitioners for efficient execution. Some mesh partitioners can map a mesh to a heterogeneous computational platform, where processor and network performance may vary. Such partitioners generally model the computational platform as a weighted graph, where the weight of a vertex gives relative processor performance, and the weight of a link indicates the relative transmission rate of the link between two processors. However, the performance of a network link is typically characterized by two parameters, bandwidth and latency, which cannot be captured in a single weight. We show that taking into account the network heterogeneity of a computational resource can significantly improve the quality of a domain decomposition obtained using graph partitioning. Furthermore, we show that taking into account bandwidth and latency of the network links is significantly better than just considering the former. This work is presented as an extension to the PaGridpartitioner, and includes a model for estimated execution time, which is used as a cost function by the partitioner but could also be used for performance prediction by application-oriented schedulers.

Parallelization of sequential programs is often daunting because of the substantial development cost involved. Previous solutions have not always been successful, partly because many try to address all types of applications. We propose a platform for parallelization of a class of applications that have similar computational structure, namely graph-structured iterative applications. iC2mpi is a unique proof-of-concept prototype platform that provides relatively easy parallelization of existing sequential programs and facilitates experimentation with static partitioning and dynamic load balancing schemes. We demonstrate with various generic application graph topologies that our platform can produce good performance with very little effort. The iC2mpi platform has a good potential for further performance improvements and for extensions to related classes of application domains.

A new algorithm is proposed for computing the discrete Fourier Transform (DFT) of purely phase encoded data acquired during Magnetic Resonance Imaging (MRI) experiments. These experiments use the SPRITE (Single Point Ramped Imaging with T 1 Enhancement) method and multiple-point acquisition, sampling data in a nonuniform manner that prohibits reconstruction by fast Fourier transform. The chirp z-transform algorithm of Rabiner, Schafer, and Rader can be combined with phase corrections to compute the DFT of this data to extremely high accuracy. This algorithm outperforms the interpolation methods that are traditionally used to process nonuniform data, both in terms of execution time and in terms of accuracy as compared to the DFT.