Search

The efficient codes can take an advantage of multiple threads and/or processing nodes to partition a work that can be processed concurrently. This can reduce the overall run-time or make the solution of a large problem feasible. This paper deals with evaluation of different parallelization strategies of assembly operations for global vectors and matrices, which are one of the critical operations in any finite element software. Different assembly strategies for systems with a shared memory model are proposed and evaluated, using Open Multi-Processing (OpenMP), Portable Operating System Interface (POSIX), and C++11 Threads. The considered strategies are based on simple synchronization directives, various block locking algorithms and, finally, on smart locking free processing based on a colouring algorithm. The different strategies were implemented in a free finite element code with object-oriented architecture OOFEM [1].

Relaxing the sequential specification of shared objects has been proposed as a promising approach to obtain implementations with better complexity. In this paper, we study the step complexity of relaxed variants of two common shared objects: max registers and counters. In particular, we consider the $k$ -multiplicative-accurate max register and the k-multiplicative-accurate counter, where read operations are allowed to err by a multiplicative factor of $k$ (for some $k\in \mathbb{N}$ ). More accurately, reads are allowed to return an approximate value $x$ of the maximum value $v$ previously written to the max register, or of the number $v$ of increments previously applied to the counter, respectively, such that $v/k\leq x\leq v. k$ . We provide upper and lower bounds on the complexity of implementing these objects in a wait-free manner in the shared memory model.

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m=n, and loose if m>n. In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O(logn) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m=(1+ϵ)⋅n and constant ϵ, they achieve a step complexity of O(loglogn). In this paper we consider tight as well as loose renaming and introduce randomized algorithms that achieve their tasks with high probability. The model assumed is the asynchronous shared-memory model against an adaptive adversary. Our algorithm for loose renaming maps n processes to a name space of size m=(1+2∕(logn)ℓ)⋅n=(1+o(1))⋅n performing O(ℓ⋅(loglogn)2) test-and-set operations. In the case of tight renaming, we present a protocol that assigns n processes to n names with step complexity O(logn), but without the overhead and impracticality of the AKS network. This algorithm utilizes modern hardware features in form of a counting device which is also described in the paper. This device may have the potential to speed up other distributed algorithms as well.

Software parallelization has gained increasing interest since the transistor manufacturing of smaller chips within an integrated circuit has begun to stagnate. This has led to the development of new processing units with an increasing number of cores. Parallelization is an optimization technique that allows the user to utilize parallel processes in order to streamline algorithm flows. This study examines the performance benefits that a passive bistatic radar system can obtain by parallelization and code refactorization. The study focuses mainly on investigating the use of parallel instructions within a shared memory model on a Central Processing Unit (CPU) with the use of an application programming interface, namely OpenMP. Quantitative data is collected to compare the runtime of the most central algorithm in the passive radar system, namely the Extensive Cancellation Algorithm (ECA). ECA can be used to suppress unwanted clutter in the surveillance signal, which purpose is to create clear target detections of airborne objects. The algorithm on the other hand is computationally demanding, which has led to the development of faster versions such as the Sliding ECA (ECA-S). Despite the ongoing development, the algorithm is still relatively computationally demanding which can lead to long execution times within the radar system. In this study, a MATLAB implementation of ECA-S is transformed to C in order to take advantage of the fast execution time of the procedural programming language. Parallelism is introduced within the converted algorithm by the use of Intel's thread methodology and then applied within two different operating systems. The study shows that a speedup can be obtained, in the programming language C, by a factor of 24 while still ensuring the correctness of the results. The results also showed that code refactorization of a MATLAB algorithm could result in 73% faster code and that C-MEX implementations are twice as slow as a C-implementation. Finally, the study pointed out that real-time can be achieved for a passive bistatic radar system with the use of the programming language C and by using parallel instructions within a shared memory model on a CPU. Parallellisering av mjukvara har fått ett ökat intresse sedan transistortillverkningen av mindre chip inom en integrerade krets har börjat att stagnera. Detta har lett till utveckling av moderna processorer med ett ökande antal av kärnor. Parallellisering är en optimeringsteknik vilken tillåter användaren att utnyttja parallella processer till att effektivisera algoritmflöden. Denna studie undersöker de tidsmässiga fördelar ett passivt bistatiskt radarsystem kan erhålla genom att, bland annat tillämpa parallellisering och omformning. Studien fokuserar främst på att undersöka användandet av parallella trådar inom det delade minnesutrymmet på en centralprocessor (CPU), detta med hjälp av applikationsprogrammeringsgränssnittet OpenMP. Kvantitativa jämförelser tas fram med hjälp av en av de mest centrala algoritmerna inom det passiva radarsystemet, nämligen Extensive Cancellation Algorithm (ECA). ECA kan används till att undertrycka oönskat klotter i övervakningssignalen, vilket har till syfte att skapa klara måldetektioner av luftföremål. Algoritmen är däremot beräkningstung, vilket har medfört utveckling av snabbare versioner som exempelvis Sliding ECA (ECA-S). Trots utvecklingen är algoritmen fortfarande relativt beräkningstung och kan medföra en lång exekeveringstid inom hela radarsystemet. I denna studie transformeras en MATLAB-implementation av ECA-S till C för att kunna dra nytta av den snabba exekeveringstiden i det procedurella programmeringsspråket. Parallellism införs inom den transformerade algoritmen med hjälp av Intels trådmetodik och appliceras sedan inom två olika operativsystem. Studien visar på en tidsmässig optimering i C med upp till 24 gånger snabbare exekeveringstid och bibehållen noggrannhet. Resultaten visade även på att en enklare omformning av en MATLAB-algoritm kunde resultera till 73% snabbare kod och att en C-MEX-implementation är dubbelt så långsam i jämförelse med en C-implementering. Slutligen pekade studien på att realtid kan uppnås för ett passivt bistatiskt radarsystem vid användandet av programmeringsspråket C och med utnyttjandet av parallella instruktioner inom det delade minnet på en CPU.

The use of hybrid scheme combining the message passing programming models for inter-node parallelism and the shared memory programming models for node-level parallelism is widely spread. Existing extensive practices on hybrid Message Passing Interface (MPI) plus Open Multi-Processing (OpenMP) programming account for its popularity. Nevertheless, strong programming efforts are required to gain performance benefits from the MPI+OpenMP code. An emerging hybrid method that combines MPI and the MPI shared memory model (MPI+MPI) is promising. However, writing an efficient hybrid MPI+MPI program -- especially when the collective communication operations are involved -- is not to be taken for granted. In this paper, we propose a new design method to implement hybrid MPI+MPI context-based collective communication operations. Our method avoids on-node memory replications (on-node communication overheads) that are required by semantics in pure MPI. We also offer wrapper primitives hiding all the design details from users, which comes with practices on how to structure hybrid MPI+MPI code with these primitives. The micro-benchmarks show that our collectives are comparable or superior to those in pure MPI context. We have further validated the effectiveness of the hybrid MPI+MPI model (which uses our wrapper primitives) in three computational kernels, by comparison to the pure MPI and hybrid MPI+OpenMP models., Comment: 14 pages. Accepted for publication in Parallel Computing

This paper introduces our research on investigating the possibility of using heterogeneous all-MPI programming for the efficient parallelization of real-world scientific applications on clusters of multicore SMP/ccNUMA nodes. The investigation is based on verifying the efficiency of parallelizing a CFD application known as MPDATA, which contains a set of stencil kernels with heterogeneous patterns. As the first step of the research, we consider the level of SMP nodes, and compare the performance achieved by the MPI Shared Memory model of MPI-3 versus the OpenMP approach. In contrast to other works, this paper aims to evaluate these two programming models in conjunction with the parallelization methodology recently proposed [1] for performance portable programming across multicore SMP/ccNUMA platforms. We show that the shared memory extension of MPI delivers portable means for implementing all steps of this methodology efficiently, to take advantages of emerging multicore ccNUMA architectures.

In this paper, we consider the collaborative editing of two-dimensional (2D) data such as handwritten letters and illustrations. In contrast to 1D case, overriding of objects can have a specific meaning in editing 2D data; e.g., we can represent the relative distance of two objects and the transparency by over-riding them. This paper considers the semantics of collaborative drawing by focusing on the overriding of objects, and proposes three editing modes based on users' strokes. Proposed editing modes are realized as a part of Android application with a careful selection of the information sharing model; e.g., we can switch the shared memory model realized by Firebase Realtime Database to a distributed shared memory realized by connecting replica nodes through WebRTC, depending on the use-case.

We investigate the fault-tolerant capability of distributed systems in anonymous and unreliable settings. In the anonymous model, processes have no identifiers and execute an identical code. The present paper assumes that processes are prone to crash failures and communicate via multi-writer/multi-reader shared registers. We study the wait-free solvability of colorless tasks in the anonymous model. Especially, we propose an anonymous full-information protocol for colorless tasks and give a topological characterization of colorless tasks that are wait-free solvable in the anonymous model. The characterization implies that the anonymity does not reduce the computational power of the asynchronous shared-memory model as long as colorless tasks are concerned. We also show that some of the existing topological arguments on the eponymous model apply to the anonymous one.

The advent of multi-/many-core processors in clusters advocates hybrid parallel programming, which combines Message Passing Interface (MPI) for inter-node parallelism with a shared memory model for on-node parallelism. Compared to the traditional hybrid approach of MPI plus OpenMP, a new, but promising hybrid approach of MPI plus MPI-3 shared-memory extensions (MPI+MPI) is gaining attraction. We describe an algorithmic approach for collective operations (with allgather and broadcast as concrete examples) in the context of hybrid MPI+MPI, so as to minimize memory consumption and memory copies. With this approach, only one memory copy is maintained and shared by on-node processes. This allows the removal of unnecessary on-node copies of replicated data that are required between MPI processes when the collectives are invoked in the context of pure MPI. We compare our approach of collectives for hybrid MPI+MPI and the traditional one for pure MPI, and also have a discussion on the synchronization that is required to guarantee data integrity. The performance of our approach has been validated on a Cray XC40 system (Cray MPI) and NEC cluster (OpenMPI), showing that it achieves comparable or better performance for allgather operations. We have further validated our approach with a standard computational kernel, namely distributed matrix multiplication, and a Bayesian Probabilistic Matrix Factorization code., Comment: 10 pages. Accepted for publication in ICPP Workshops 2019

Recent developments in computer hardware bring in new opportunities in numerical mod-elling. Traditional simulation codes run sequentially on computers with a single processing unit,where only one instruction can be processed at any moment in time. The performance of single pro-cessing units is reaching the physical limits, given by transmission delays and heat build-up on thesilicon chips. The current trend in technology is parallel processing, relying on the simultaneous useof multiple processing units to solve given problem. The efficient utilization of parallel computingresources requires development of new algorithms and techniques allowing to decompose the giventask into pieces of work that can be processed simultaneously.This contribution focuses on parallelization of vector assembly operation, which is one of thecritical operations in any finite element software. The aim of presented work is to propose differentapproaches to parallelization of this operation and to evaluate their efficiency. In this contribution,we focus on shared memory programming model, where individual processes/tasks share a commonaddress space, which they read and write to asynchronously. Open Multi-Processing (OpenMP) andPortable Operating System Interface (POSIX) Threads programming models are used to implementdifferent variants of parallel assembly operations. The efficiency of implemented approaches is eval-uated on a selected benchmark problem, comparing computation times and obtained speed-ups.

Since the early days of the shared memory model for distributed computing, researchers have sought a simple and precise characterization of an object's ability to implement other objects in a wait-free manner.The first candidate for such a characterization was the object's consensus number [14]. But a characterization based on consensus numbers is not precise: there are pairs of objects with the same consensus number that are not equivalent (i.e., one cannot be implemented by instances of the other and registers). This was first shown for non-deterministic objects [24] and much later for deterministic objects as well [2].A more recent candidate for such a characterization is the object's set agreement power [10]. In PODC 2017, it was shown that this characterization is also not precise: there are two objects with the same set agreement power that are not equivalent [6]. One of these two objects, however, is non-deterministic. So this left open one remaining final question: when restricted to deterministic objects, does the set agreement power of an object fully characterize its ability to implement other objects? More precisely: are any two deterministic objects with the same set agreement power equivalent? In this paper, we show the answer is again no. In fact, we prove the following stronger result: every level n ≥ 2 of Herlihy's consensus hierarchy [14] contains two deterministic objects with the same set agreement power that are not equivalent (i.e., one of these two objects cannot be implemented using instances of the other and registers).We also leverage the above result and a result in [12] to show that in any system with n > 2 processes, there is a deterministic wait-free object that is not equivalent to any wait-free task.

Existing n-process randomized wait-free (and obstruction-free) consensus protocols from registers all use at least n registers. In 1992, it was proved that such protocols must use Omega(sqrt(n)) registers. Recently, this was improved to Omega(n) registers in the anonymous setting, where processes do not have identifiers. Closing the gap in the general case, however, remained an open problem. We resolve this problem by proving that every randomized wait-free (or obstruction-free) consensus protocol for n processes must use at least n-1 registers.

Parallel programming models and paradigms are increasingly becoming more expressive with a steady increase in the number of cores that can be placed on a single chip. Concurrent data structures for shared memory parallel pro- grams are now being used in operating systems, middle-ware, and device drivers. In such a shared memory model, processes communicate and synchronize by applying primitive operations on memory words. To implement concurrent data structures that are linearizable and possibly lock-free or wait-free, it is often necessary to add additional information to memory words in a data structure. This additional information can range from a single bit to multiple bits that typically represent thread ids, request ids, timestamps, and other application dependent fields. Since most processors can perform compare-And-Set (CAS) or load-link/store-conditional (LL/SC) operations on only 64 bits at a time, current approaches either use some bits in a memory word to pack additional information (packing), or use the bits to store a pointer to an object that contains additional information (redirection), and the original data item. The former approach restricts the number of bits for each additional field and this reduces the range of the field, and the latter approach is wasteful in terms of space. We propose a novel and universal method called a memory word expander in this paper. It caches information for a set of memory locations that need to be augmented with additional information. It supports traditional atomic get, set, and CAS operations, and tries to maintain state for a minimum number of entries. We experimentally demonstrate that it is possible to reduce the runtime memory footprint by 20-35% for algorithms that use redirection. For algorithms that use packing, the use of the EXPANDER can make them feasible. The performance overhead is within 2-13% for 32 threads. When we compare the performance of the EXPANDER based non-blocking algorithms with the version that uses locks, we have a performance gain of at least 10-100X.

Targeting the development of new biochip platforms capable of autonomously sequencing and aligning biological sequences, a new multicore processing structure is proposed in this manuscript. This multicore structure makes use of a shared memory model and multiple instantiations of a novel application-specific instruction-set processor (ASIP) to simultaneously exploit both fine and coarse-grained parallelism and to achieve high performance levels at low-power consumption. The proposed ASIP is built by extending the instruction set architecture of a synthesizable processor, including both general and special-purpose single-instruction multiple-data instructions. This allows an efficient exploitation of fine-grained parallelism on the alignment of biological sequences, achieving over $30\times $ speedup when compared with sequential algorithmic implementations. The complete system was prototyped on different field-programmable gate array platforms and synthesized with a 90-nm CMOS process technology. Experimental results demonstrate that the multicore structure scales almost linearly with the number of instantiated cores, achieving performances similar to a quad-core Intel Core i7 3820 processor, while using $25\times $ less energy.

We present a new shared memory model, SF shared memory model. In this model, the actions of each node are partitioned into slow actions and fast actions. By contrast, the traditional shared memory model only includes fast actions. Intuitively, slow actions can utilize slightly stale state information to execute successfully. However, fast actions require that the state information they use is most recent.We show that the use of slow actions can substantially benefit in improving performance of programs from the shared memory model to WAC model that has been designed for sensor networks. To illustrate this, we use three protocols concerning problems that need to be solved in sensor networks. We show that under various message loss probabilities, densities, etc., slow actions can improve the performance substantially, since slow actions reduce the performance penalty of fast actions under heavy message loss environments. Moreover, the effectiveness of the slow action increases when there is a higher probability of message loss. None of the existing computational models consider message loss/collision in the distributed systems.WAC model is a model that considers message loss in distributed systems. However, it reduces the performance.Our work is a variation of the shared memory model, namely SF shared memory model.It can improve the performance in the presence of message loss.We present an analytical proof (and evaluations for three protocols) for our SF model.

This paper explores the possibility of using multi-core programming model that implements the Cascade correlation neural networks technique (CCNNs), to enhance the classification phase of 3D facial recognition system, after extracting robust and distinguishable features. This research provides a comprehensive summary of the 3D facial recognition systems, as well as the state-of-the- art for the Parallel Cascade Correlation Neural Networks methods (PCCNNs). Moreover, it highlights the lack of literature that combined between distributed and shared memory model which leads to novel possibility of taking advantage of the strengths of both approaches in order to construct an efficient parallel computing system for 3D facial recognition.

Shared Memory stands out as a sine qua non for parallel programming of many commercial and emerging multicore processors. It optimizes patterns of communication that benefit common programming styles. As parallel programming is now mainstream, those common programming styles are challenged with emerging applications that communicate often and involve large amount of data. Such applications include graph analytics and machine learning, and this paper focuses on these domains. We retain the shared memory model and introduce a set of lightweight in-hardware explicit messaging instructions in the instruction set architecture (ISA). A set of auxiliary communication models are proposed that utilize explicit messages to accelerate synchronization primitives, and efficiently move computation towards data. The results on a 256-core simulated multicore demonstrate that the proposed communication models improve performance and dynamic energy by an average of 4x and 42% respectively over traditional shared memory.

OpenMP is a shared memory programming model which supports the offloading of target regions to accelerators such as NVIDIA GPUs. The implementation in Clang/LLVM aims to deliver a generic GPU compilation toolchain that supports both the native CUDA C/C++ and the OpenMP device offloading models. There are situations where the semantics of OpenMP and those of CUDA diverge. One such example is the policy for implicitly handling local variables. In CUDA, local variables are implicitly mapped to thread local memory and thus become private to a CUDA thread. In OpenMP, due to semantics that allow the nesting of regions executed by different numbers of threads, variables need to be implicitly \emph{shared} among the threads of a contention group. In this paper we introduce a re-design of the OpenMP device data sharing infrastructure that is responsible for the implicit sharing of local variables in the Clang/LLVM toolchain. We introduce a new data sharing infrastructure that lowers implicitly shared variables to the shared memory of the GPU. We measure the amount of shared memory used by our scheme in cases that involve scalar variables and statically allocated arrays. The evaluation is carried out by offloading to K40 and P100 NVIDIA GPUs. For scalar variables the pressure on shared memory is relatively low, under 26\% of shared memory utilization for the K40, and does not negatively impact occupancy. The limiting occupancy factor in that case is register pressure. The data sharing scheme offers the users a simple memory model for controlling the implicit allocation of device shared memory.