Many core systems are basically designed for applications having large data parallelism. Strassen Matrix Multiply (MM) can be formulated as a depth first (DFS) traversal of a recursion tree where all cores work in parallel on computing each of the NxN sub-matrices that reduces storage at the detriment of large data motion to gather and aggregate the results. We propose Strassen and Winograd algorithms (S-MM and W-MM) based on three optimizations: a set of basic algebra functions to reduce overhead, invoking efficient library (CUBLAS 5.5), and parameter-tuning of parametric kernel to improve resource occupancy. On GPUs, W-MM and S-MM with one recursion level outperform CUBLAS 5.5 Library with up to twice as faster for large arrays satisfying N>=2048 and N>=3072, respectively. Compared to NVIDIA SDK library, S-MM and W-MM achieved a speedup between 20x to 80x for the above arrays. The proposed approach can be used to enhance the performance of CUBLAS and MKL libraries.

Massively parallel computing is applied extensively in various scientific and engineering domains. With the growing interest in many-core architectures and due to the lack of explicit support for inter-block synchronization specifically in GPUs, synchronization becomes necessary to minimize inter-block communication time. In this paper, we have proposed two new inter-block synchronization techniques: 1) Relaxed Synchronization, and 2) Block-Query Synchronization. These schemes are used in implementing numerical iterative solvers where computation/communication overlapping is one used optimization to enhance application performance. We have evaluated and analyzed the performance of the proposed synchronization techniques using Jacobi Iterative Solver in comparison to the state of the art inter-block lock-free synchronization techniques. We have achieved about 1–8% performance improvement in terms of execution time over lock-free synchronization depending on the problem size and the number of thread blocks. We have also evaluated the proposed algorithm on GPU and MIC architectures and obtained about 8–26% performance improvement over the barrier synchronization available in OpenMP programming environment depending on the problem size and number of cores used.

In the recent years, the Graphics Processing Units (GPUs) have gained popularity for general purpose applications, immensely outperforming traditional optimized CPU based implementations. A class of such applications implemented on GPUs to achieve faster execution than CPUs include cryptographic techniques like the Advanced Encryption Standard (AES) which is a widely deployed symmetric encryption/decryption scheme in various electronic communication domains. With the drastic advancements in electronic communication technology, and growth in the user space, the size of data exchanged electronically has increased substantially. So, such cryptographic techniques become a bottleneck to fast transfers of information. In this work, we implement the AES-128 ECB Encryption on two of the recent and advanced GPUs (NVIDIA Quadro FX 7000 and Tesla K20c) with different memory usage schemes and varying input plaintext sizes and patterns. We obtained a speedup of up to 87x against an advanced CPU (Intel Xeon X5690) based implementation. Moreover, our experiments reveal that the different degrees of pattern repetitions in input plaintext affect the encryption performance on GPU.

Matrix Transposition is an important linear algebra procedure that has deep impact in various computational science and engineering applications. Several factors hinder the expected performance of large matrix transpose on Graphic Processing Units (GPUs). The degradation in performance involves the memory access pattern such as coalesced access in the global memory and bank conflict in the shared memory of streaming multiprocessors within the GPU. In this paper, two matrix transpose algorithms are proposed to alleviate the aforementioned issues of ensuring coalesced access and conflict free bank access. The proposed algorithms have comparable execution times with the NVIDIA SDK bank conflict - free matrix transpose implementation. The main advantage of proposed algorithms is that they eliminate bank conflicts while allocating shared memory exactly equal to the tile size (T × T) of the problem space. However, to the best of our knowledge an extra space of Tx(T +1) needs to be allocated in the published research. We have also applied the proposed transpose algorithm to recursive Gaussian implementation of NVIDIA SDK and achieved about 6% improvement in performance.

Reliable, fast, and power aware communication is needed for Ad-Hoc wireless networks. Current techniques based on client-server and Publish/Subscribe communication models are not suitable in multi-robot systems and generally for mobile applications. For this we propose a reliable peer-to-peer protocol based on a UDP Broadcast and Token Passing (UBTP). The protocol is implemented on a WLAN using the Stargate embedded system. For this, a customized UDP protocol with an imperative Poll-based communication is proposed. The protocol is implemented using (1) a communication thread (TC) and (2) a processing thread (TP). A test bed system which allows modules to run TC and TP, in addition to the generation of broadcast request is presented. We used symmetric code in each node. Evaluation reports the distribution of auction completion times for peer-to-peer operations. The evaluation reveals: (1) response times are comparable to UBTP operated at head node, (2) improved degree of reliability as at most 2 steps are sufficient for auctioning seven nodes, (3) proved fairness, and (4) comparable power consumption to simple UBTP.

Humanoid robots are enjoying increasing popularity as a research tool and education tool. The ultimate goal of the international RoboCup Initiative is to build a humanoid soccer team which beats a human World Cup Champion team in 2050. Despite impressive achievements of some teams, the overall performance of the soccer playing humanoids is still far from perfect. The robots sometimes show instability while walking, fail to kick the ball or defend against shots not taken. In this study we present a geometrical model for the walking legs of the Kondo KHR-1 humanoid robot. The model allows to establish the relationships between a set of function walking motion controls and that of the leg controlled angles. Furthermore, we use the German team SimRobot to program the soccer scene and for the analysis of Kondo walking motion. For this we developed a 3D model as part of the SimRobot controller. A set of synthesized walking motions were designed. The result is a library of motions which are: 1) Walking Forward 2) Walking Backwards 3) Step right/left 4) Turn right/left 5) Swat right/left 6) Kick right/left 7) Bow 8) Push-ups. The library is useful to facilitate soccer behavior programming for preparing the students to the RoboCup competition.

The class scheduling problem can be modeled by a graph where the vertices and edges represent the courses and the common students, respectively. The problem is to assign the courses a given number of time slots (colors), where each time slot can be used for a given number of class rooms. The Vertex Coloring (VC) algorithm is a polynomial time algorithm which produces a conflict free solution using the least number of colors [9]. However, the VC solution may not be implementable because it uses a number of time slots that exceed the available ones with unbalanced use of class rooms. We propose a heuristic approach VC* to (1) promote uniform distribution of courses over the colors and to (2) balance course load for each time slot over the available class rooms. The performance function represents the percentage of students in all courses that could not be mapped to time slots or to class rooms. A randomized simulation of registration of four departments with up to 1200 students is used to evaluate the performance of proposed heuristic.

A three-level architecture for a team of autonomous cooperative robots has been proposed. A dynamic Joint-Commitment scheme is proposed to support the formulation of relational behaviors for cooperative robots playing soccer. Teamwork between two robots which know from each other that they are committed to a relational behavior may pass the ball from one robot to another, receive the ball and kick, and handle exceptions. The joint commitment is established based on a finite state machine and a messaging system to: (1) synchronize the pass behavior, (2) reiterate the process and extend the pass to another partner, or (3) break the commitment and search for a new partner depending on dynamic game conditions. To provide dynamic joint-commitment and needed synchronization a fast, reliable, and power aware communication model is needed for Ad-Hoc wireless networks forming a cooperating multi-robot system. Current techniques are based on client-server, Publish/Subscribe, and Peer/Peer communication which are not suitable. For this we implemented and evaluated an auction based communication model based on (1) TCP Peer to Peer Scheme, (2) UDP Peer to Peer (UPTP) Scheme, and (3) UDP Broadcast and Token Passing (UBTP) scheme. Evaluation reports the distribution of auction completion times and power consumption for auction-based and peer-to-peer communication.

In the pipeline banyan (PB) the reservation cycle in the control plane is made several times faster than payload transmission in data plane. This enables pipelining of multiple banyans. It is observed that the service rate is relatively low in the PB due to the banyan. For this, we present a scalable pipelined ATM switch employing a family of dilated banyan (DB) networks. A DB can be engineered between two extremes: (1) a low-cost banyan with internal and external conflicts; or (2) a high-cost conflict-free fully-connected network with multiple outlets. Increasing the dilation degree reduces path conflicts, which produces noticeable increase in service rate due to increase in throughput and decrease in path delay. Simulation of PDB was carried out under uniform traffic and simulated ATM traffic. We study performance under variation in the load, buffer size, and number of data planes. We show that performance of the switch is not degradable under ATM traffic with temporal and spatial burstiness generated by using the ON-OFF traffic model. A 256-input PDB can deliver up to 3.3 times the service rate of the PB with linear increase in hardware cost.

We present a compiler optimization approach that uses the simulated evolution (SE) paradigm to enhance the finish time of heuristically scheduled computations with communications. This is especially beneficial to the class of synchronous dataflow computations which are generally compiled once and run many times over different data sets. Unlike genetic approaches which generally use task swapping to create differential variations, our approach consists of adding pseudo-edges to the task graph to guide the scheduler in the alignment and clustering of dominant tasks. Added edges alter only the task graph without modifying the scheduler, which provides useful flexibility in the implementation of compiler optimization options. The intelligence of iterative methods is used by SE to reduce the run-time and to avoid local minima by using the hill-climbing property of search-based methods. Evaluation is carried out on a wide variety of computation graphs which are studied for different levels of communication granularities and task parallelisms. A statistical analysis of results shows that edge-addition SE is capable of finding near-optimum schedules as well as outperforming other known heuristics such as ETF, DLS and GLS. Moreover, this approach is useful in complementing heuristics whose solution finish time cannot be guaranteed for arbitrary communication and parallelism. Since the performance of most scheduling heuristics is profile-sensitive, optimizing the heuristic solutions through edge-addition SE provides increased confidence in the quality of the solution.

In the pipeline banyan (PB), the reservation cycle in the control plane is made several times faster than payload transmission in data plane. This enables pipelining multiple banyans. It is observed that the ratio of throughput to switching delay (service rate) is relatively low in the PB due to the banyan. For this, we present a scalable pipelined asynchronous transfer mode (ATM) switch architecture employing a family of dilated banyan (DB) networks together with their complexity analysis and performance. A DB can be engineered between two extremes: (1) a low-cost banyan with internal and external conflicts, or (2) a high-cost conflict-free fully connected network with multiple outlets. Between the two extremes lies a family of DBs having different switching delays and throughputs. Increasing the dilation degree reduces path conflicts, which produces noticeable increase in service rate due to increase in throughput and decrease in path delay. Compared to PB, the pipelined dilated banyan (PDB) requires smaller number of data planes for the same throughput, or provides higher throughput for a given number of data planes. Simulation of PDB is carded out under uniform traffic and simulated ATM traffic. We study the switch performance while varying the load, buffer size, and number of data planes. To analyze the robustness of the switch, we show that performance is not degradable under ATM traffic with temporal and spatial burstiness generated using the on-off model. The PDB is scalable with respect to service rate and can be engineered with respect to: (1) cell loss rate; (2) hardware resources; (3) size of buffers; (4) switching delays; and (5) delay incurred to higher priority traffic. The PDB can deliver up to 3.5 times the service rate of the PB with only linear increase in hardware cost.

We present a novel ATM switch called parallel-tree Banyan switch fabric (PTBSF) that consists of parallel Banyans arranged in a tree topology. Packets enter at the topmost Banyan. Internal conflicts are eliminated by using a conflict free 3/spl times/4 switching element which distributes conflicting cells over different Banyans. Thus, cell loss may occur only at the lowest Banyan. Increasing the number of Banyans leads to noticeable decrease in the cell loss rate. The switch can be engineered to provide arbitrarily high throughput and low cell loss rate without the use of input buffering nor cell pre-processing. The performance of the switch is evaluated analytically under uniform traffic load and by simulation under a variety of ATM traffic loads. Compared to other proposed architectures, the switch exhibited stable and excellent performance with respect to cell loss and switching delay for all studied conditions as required by ATM traffic sources. The advantages of PTBF are modularity, regularity, self-routing, low processing over head, high throughput and robustness under a variety of ATM traffic conditions.

The serialization of memory accesses is a major limiting factor in high performance SIMD computers. The data patterns or templates that are accessed by a program can be perceived by the compiler, and, therefore, the design of dynamic storage schemes that minimize conflicts may dramatically improve performance. The problem of finding storage schemes that minimize the access time of arbitrary sets of power-of-two data patterns is proved to be NP-complete. We propose linear address transformations that can be dynamically applied by each processing element for mapping array references onto memories. An efficient approach for combining the constraints of different access patterns into one single linear address transformation is presented. We prove that finding the transformation that minimizes the access time is reducible to N-coloring, where N is the number of parallel memories. Using coloring heuristics, storage schemes are investigated with respect to minimizing the implementation cost (perfect storage) and overall access conflicts (semiperfect storage). Results show that the perfect-storage may deviate on the average by 20% from the optimum access time in the case of 10 arbitrary data patterns and 16 memories. However, semiperfect schemes lead to dramatic reduction of the degree of conflict compared to perfect-schemes. The proposed heuristic storage largely outperforms interleaving and row-column-diagonals storages. The method can be implemented as compiler procedure for synthesizing storage schemes that promote parallel access to arbitrary sets of data patterns.

Finding general XOR-schemes to minimize memory and network contention for accessing arrays with arbitrary sets of data templates is presented. A combined XOR-matrix is proposed together with a necessary and sufficient condition for conflict-free access. We present a new characterization of the baseline network. Finding an XOR-matrix for combined templates is shown to be an NP-complete problem. A heuristic is proposed for finding XOR-matrices by determining the constraints of each template-matrix and solving a set of simultaneous equations for each row. Evaluation shows significant reduction of memory and network contention compared to interleaving and to static row-column-diagonals storage.

Using knowledge on computation, communication, and multiprocessor topology, a class of global priority-based scheduling heuristics, called generalized list scheduling (GLS) is proposed. Task-priority is defined as the completion time of the task following backward scheduling the computation over the multiprocessor by using the best local heuristic. GLS scheduling consists of using the task-priority in forward, graph-driven scheduling. Evaluation of local (ETF) and GLS heuristics is carried out by altering over the communication, parallelism, and system topology. Analysis shows that local heuristics rely on locally maximizing the efficiency and gives acceptable solutions only when the parallelism is large enough to cover the communication (bounded speedup). GLS scheduling outperforms the local approaches versus change in parallelism, communication, and network topology. The time complexity of GLS heuristics is O(pn/sup 2/), where p and n are the number of processors and that of the tasks, respectively.>

This paper presents a Data-Distributed Execution (DDE) approach that exploits iteration-level parallelism in loops operating over arrays.

The EM-4 is a supercomputer that offers very fast interprocessor communication and support for multithreading. In this paper we demonstrate that the EM-4, together with an automatic parallelization technique referred to as Data-Distributed Execution (DDE), offer a computing environment in which large portions of scientific code can be executed without the need for any explicit parallelism.

The author studies dynamic scheduling of computational tasks with communication costs using nonuniform memory access architecture. The computing model assumes that data transfer can be partitioned into parallel and sequential parts with respect to the task execution. A scheduling heuristic, called least-communication (LC), together with a two-level scheduler is proposed in an attempt to minimize the finish time. The LC selects the task that removes the largest amount of remaining data transfer, if no such tasks are available the task that has been ready to run at the earliest is selected first. The time complexity of LC is O(n/sub 2/). Testing the finish time of LC and first-come first-served scheduling (FCFS) shows that LC is useful for tasks having moderate granularity and whose computation and communication requirements vary widely for different data sets.>

A lower bound on the number of processors and finish time for the problem of scheduling precedence graphs with communication costs is presented. The notion of the earliest starting time of a task is formulated for the context of lower bounds. A lower bound on the completion time is proposed. A task delay which does not increase the earliest completion time of a schedule is defined. Each task can then be scheduled within a time interval without affecting the lower bound performance on the finish time. This leads to definition of a new lower bound on the number of processors required to process the task graph. A derivation of the minimum time increase over the earliest completion time is also proposed for the case of a smaller number of processors. A lower bound on the minimum number of interprocessor communication links required to achieve optimum performance is proposed. Evaluation had been carried out by using a set of 360 small graphs. The bound on the finish time deviates at most by 5% from the optimum solution in 96% of the cases and performs well with respect to the minimum number of processors and communication links.>