Parallel Processing Letters

Basic Linear Algebra Subprograms (BLAS) and Linear Algebra Package (LAPACK) form basic building blocks for several High Performance Computing (HPC) applications and hence dictate performance of the HPC applications. Performance in such tuned packages is attained through tuning of several algorithmic and architectural parameters such as number of parallel operations in the Directed Acyclic Graph of the BLAS/LAPACK routines, sizes of the memories in the memory hierarchy of the underlying platform, bandwidth of the memory, and structure of the compute resources in the underlying platform. In this paper, we closely investigate the impact of the Floating Point Unit (FPU) micro-architecture for performance tuning of BLAS and LAPACK. We present theoretical analysis for pipeline depth of different floating point operations like multiplier, adder, square root, and divider followed by characterization of BLAS and LAPACK to determine several parameters required in the theoretical framework for deciding optimum pipeline depth of the floating operations. A simple design of a Processing Element (PE) is presented and shown that the PE outperforms the most recent custom realizations of BLAS and LAPACK by 1.1X to 1.5X in GFlops/W, and 1.9X to 2.1X in Gflops/mm². Compared to multicore, General Purpose Graphics Processing Unit (GPGPU), Field Programmable Gate Array (FPGA), and ClearSpeed CSX700, performance improvement of 1.8-80x is reported in PE.

Clustering is an effective technique that can be used to analyze and extract useful information from large biological networks. Popular clustering solutions often require user input for several algorithm options that can seem very arbitrary without experimentation. These algorithms can provide good results in a reasonable time period but they are not above improvements. We present a local search based clustering algorithm free of such required input that can be used to improve the cluster quality of a set of given clusters taken from any existing algorithm or clusters produced via any arbitrary assignment. We implement this local search using a modern GPU based approach to allow for efficient runtime. The proposed algorithm shows promising results for improving the quality of clusters. With already high quality input clusters we can achieve cluster rating improvements upto to 33%.

We present an intelligent scheduling framework which takes as input a set of OpenCL kernels and distributes the workload across multiple CPUs and GPUs in a heterogeneous multicore platform. The framework relies on a Machine Learning (ML) based frontend that analyzes static program features of OpenCL kernels and predicts the ratio in which kernels are to be distributed across CPUs and GPUs. The framework provides such static analysis information along with system state information like runtime availability details of computing cores using well defined programming interfaces. Such interfaces are to be utilized by a user specified scheduling strategy. Given such a scheduling strategy, the framework generates device specific binaries and dispatches them across multiple devices in the heterogeneous platform as per the strategy. We test our scheduling framework extensively using different OpenCL task mixes of varying sizes and computational nature. Along with the scheduling framework, we propose a set of novel partition-aware scheduling strategies for heterogeneous multicores. Our proposed approach yields considerably better results in terms of schedule makespan when compared with the current state of the art ML based methods for scheduling of OpenCL workloads across heterogeneous multicores.

A parallel algorithm for prefix computation on $N$ data elements mapped on a Multi Mesh (MM) network of $N=n^4$ processing elements is presented here. The time required by the proposed algorithm is significantly less than that by any of the existing algorithms for prefix computation on mesh-like architectures due to the specific interconnection pattern used in the MM network. The proposed technique requires $O(N^{1/4})$ time for data communication and $O(log{N}^{1/4})$ time for computation, when mapped on a MM network constituted by $N^{1/2}$ meshes, each of size $N^{1/4}\times N^{1/4}$. The data communication time in the proposed algorithm is less than the prefix sum algorithm proposed in extended Multi Mesh. To be precise, instead of $(13N^{1/4}-5)\tau$ communication time the proposed algorithm requires a data communication time of $7.5N^{1/4}\tau$ only. Moreover, the proposed parallel algorithm does not need any extra inter block links as used in the extended Multi Mesh.

Traffic capture and analysis is key to many domains including network management, security and network forensics. Traditionally, it is performed by a dedicated device accessing traffic at a specific point within the network through a link tap or a port of a node mirroring packets. This approach is problematic because the dedicated device must be equipped with a large amount of computation and storage resources to store and analyze packets. Alternatively, in order to achieve scalability, analysis can be performed by a cluster of hosts. However, this is normally located at a remote location with respect to the observation point, hence requiring to move across the network a large volume of captured traffic. To address this problem, this paper presents an algorithm to distribute the task of capturing, processing and storing packets traversing a network across multiple packet forwarding nodes (e.g., IP routers). Essentially, our solution allows individual nodes on the path of a flow to operate on subsets of packets of that flow in a completely distributed and decentralized manner. The algorithm ensures that each packet is processed by n nodes, where n can be set to 1 to minimize overhead or to a higher value to achieve redundancy. Nodes create a distributed index that enables efficient retrieval of packets they store (e.g., for forensics applications).

Finally, the basic principles of the presented solution can also be applied, with minimal changes, to the distributed execution of generic tasks on data flowing through a network of nodes with processing and storage capabilities. This has applications in various fields ranging from Fog Computing, to microservice architectures and the Internet of Things.