Graph Pattern Matching (GPM) is a computationally demanding workload essential for modern data analytics. While emerging systems offer massive performance, they suffer from a fundamental throughput mismatch. CPU-centric systems leverage large host memory but are constrained by limited arithmetic instruction throughput during intensive set intersection operations. Conversely, GPU-accelerated systems offer massive compute power but are strictly bound by PCIe interconnect bandwidth. When processing large-scale graphs that exceed device memory, the data transfer throughput lags significantly behind the device’s consumption rate, leaving compute engines starved.

In kernel, the driver code is much more than the core code, thus having a larger attack surface. Especially for the untrusted drivers without source code, they may come from the hot-plug hardware or the user without security knowledge. Traditional isolation methods require analyzing source code to set checkpoints in the driver for control flow protection, which are not available for closed-source drivers. Evenworse, the existing isolation methods can only prevent the hijacked control flows entering/existing drivers, while they cannot discover the illegal control flows inside drivers. Although the kernel address space location randomization (KASLR) can defend against control flow hijacking, it can be bypassed by code probes. In response to these issues, this paper proposes a novel method Dbox to isolate and detect the untrusted drivers whose source code is unavailable. Dbox creates a light hypervisor to monitor and analyze the untrusted driver's behavior without relying on source code. It isolates the untrusted driver in a private space and dynamically changes its virtual space through a sliding space mechanism. Under the protection of Dbox, all control flows jumping to/from untrusted drivers can be detected. Experiments and analysis show that Dbox has good protection against code probes, kernel rootkits and code reuse attacks, and the overhead introduced to the operating system is less than 3.6% in general scenarios.

Memristor crossbar-based computing-in-memory (CIM) has garnered significant attention for accelerating deep neural networks (DNNs). Although practical operation unit (OU)-based designs incur abundant repetitive computations, recent studies propose sharing mechanisms, where redundant computations are replaced with data transfers. However, existing sharing approaches carry a heavy burden in terms of storage and energy in practical implementation. To alleviate this problem, this paper proposes a resource-efficient scheme for weight pattern sharing (ReShare). A pattern reorder algorithm is introduced to facilitate the asynchronous running of computations and sharing, which circumvents the bottleneck posed by the output buffer in a conventional sharing scheme. In addition, ReShare enables block write operations to reduce write costs. Our evaluation across four DNN models demonstrates that the proposed ReShare has a lighter overhead in energy and storage while simultaneously enhancing performance. Specifically, ReShare can achieve 1.66 × speedup, 30.7% energy saving, and 49.5% storage reduction compared to the state-of-the-art weight sharing method.

Address space layout randomization (ASLR) can hide code addresses, which has been widely adopted by security solutions. However, code probes can bypass it. In real attack scenarios, a single code probe can only obtain very limited code information instead of the information of the entire code segment. So, randomizing the entire code segment is unnecessary. How to minimize the size of the randomized object is a key to reducing the complexity and overhead for ASLR methods. Moreover, ASLR needs to be completed between the time after code probe occurs and before the probed code is used by attackers, otherwise it is meaningless. How to select an appropriate randomization time point is a basic condition for achieving effective address hiding. In this paper, we propose a runtime partial randomization method RandFun. It only randomizes the probed function with parallel threads. And the randomization is performed when and only when potential code probes are detected. In addition, RandFun can protect the probed code from being used as gadgets, whether during or after randomization. Experiments and analysis show RandFun has a good defense effect on code probes and only introduces 1.6% overhead to CPU.

Link analysis is a fundamental task for graph analytics, as it enables the identification of important nodes and patterns in the graph. Link analysis algorithms typically require traversing the graph and accessing the links of each node. However, for graphs with a skewed degree distribution, the computing efficiency of link analysis is severely constrained due to irregular connectivity, which results in randomized memory accesses and high cache miss ratio.

Profile-guided optimization (PGO) is an advanced technique used to improve the performance of Relational Databases (RDBs). However, the most common strategy is to perform profiling on the production environment, which can lead to instability and performance loss for the Database System. To address this issue, we propose an offline profiling strategy that uses a query reduction strategy to obtain a reduced query set from the production environment's log file. We then run this sample on an offline test environment to collect profile data and use it to conduct function reorder optimization. To evaluate our approach, we compared the performance improvements achieved by running a reduced query set and a full query set on a MYSQL database. We generated function call graphs for both query sets and observed that the performance improvement achieved by the reduced query set was slightly lower than that of the full query set. These results demonstrate the effectiveness of our approach and highlight the potential benefits of offline profiling strategies for improving the performance of RDBs in production environments, while also avoiding performance losses and increasing stability.

Recent advances in computer architecture significantly enhance the computational capacity of multicore systems. It allows large-scale graphs to be processed inside a single machine. Nevertheless, the irregular processing pattern of graph-structured data constrains the hardware resources from being productively utilized. In this paper, we investigate the constraints in two aspects: workload imbalance and parallel inefficiency. When a graph analytics algorithm is multithreaded, the thread time is highly diversified, indicating an uneven work distribution. Also, the intensive thread contention lowers the computing capacity of CPU cores, thereby hindering the effective utilization of CPU resources. To address these challenges, we present a proactive graph caching strategy that unequally segments graph components into cache-able subsets of varying sizes, namely Syze. First, the computational loads of cache-sized subgraphs are estimated. Then, the demanding subgraphs are further subdivided until certain threshold is met. Moreover, during the propagation of updates, a fraction of vertex ID (i.e., several bits) are encoded to facilitate the communication between subgraphs. As a result, Syze is able to balance the workloads amongst the logical cores by shortening the longest thread execution time. Meanwhile, it alleviates thread contention and thus elevates the parallel efficiency of multicores. Compared with well-optimized Ligra, Gemini and GPOP, Syze achieves accelerations by up to$17.76\times$,$11.67\times$and$2.81\times$respectively. Additionally, the side effects of Syze are evaluated, including raised cache misses and memory accesses. They play a trivial role in deciding the overall performance, as their costs are far outweighed by the gains from the even distribution of workloads and the improved utilization of multicores.Author: Please confirm or add details for any funding or financial support for the research of this article. ?>

Modern security methods use address space layout randomization (ASLR) to defend against code reuse attacks (CRAs). However, code probing can still obtain the content and address of the code through code probing. Code probing invalidates the widely used ASLR methods, causing researchers to lose confidence in them. On the contrary, we believe the ASLR is still effective, if it has anti-probing capability. To enhance the anti-probing capability of ASLR and defense CRAs, this paper proposes an anti-probing method MProbe. First, it detects the code probing activities of attackers, including address probing and content probing. Next, the execution permission of the probed code will be de-enabled in the original address space. At the same time, the equivalent code block in a random address space will replace the probed code. Finally, new security strategies are used to prevent the probed code blocks from being used as gadgets. Experiments and analysis show that MProbe has a good defense effect against CRAs based on code probing, and only introduces less than 3% performance overhead to the operating system (OS).

Profile-guided optimization (PGO) remains one of the most popular optimization strategies in code generation optimization. Function reordering is an essential step for profile-guided optimization. The state-of-the-art function reordering method performs on a unidirectional function call graph where nodes and edges define functions and caller-callee pairs. Each edge is labeled by its call frequency. However, we demonstrate that a bidirectional function call graph can represent the memory call better. We use a reinforcement learning algorithm SARSA to choose the appropriate order of functions by maximizing the total numbers of the function call through a bidirectional function call graph. In this paper, we use a self-developed tool to reordering functions. We first illustrate how our RL-based algorithm generates a new function order. Then we evaluate three algorithms on various applications, including Redis, Protobuf, and SPEC CPU benchmark. Our experiment results indicate that the new algorithm outperforms the other two algorithms in various applications, improving the resulting performance of practical applications. Especially on Redis, the performance is improved by 4.2% on SARSA, which is better than C3(3.4%) and ph (2.8%).

In a shared-memory multicore system, the intrinsic irregular data structure of graphs leads to poor cache utilization, and therefore deteriorates the performance of graph analytics. To address the problem, prior works have proposed a variety of lightweight reordering methods with focus on the optimization of cache locality. However, there is a compromise between cache locality and workload balance. Little insight has been devoted into the issue of workload imbalance for the underlying multicore system, which degrades the effectiveness of parallel graph processing. In this work, a measurement approach is proposed to quantify the imbalance incurred by the concentration of vertices. Inspired by it, we presentCache-aware Reorder (Corder), a lightweight reordering method exploiting the cache hierarchy of multicore systems. At the shared-memory level, Corder promotes even distribution of computation loads amongst multicores. At the private-cache level, Corder facilitates cache efficiency by applying further refinement to local vertex order. Comprehensive performance evaluation of Corder is conducted on various graph applications and datasets. Experimental results show that Corder yields speedup of up to$2.59\times$and on average$1.45\times$, which significantly outperforms existing lightweight reordering methods. To identify the root causes of performance boost delivered by Corder, multicore activities are investigated in terms of thread behavior, cache efficiency, and memory utilization. Statistical analysis demonstrates that the issue of imbalanced thread execution time dominates other factors in determining the overall graph processing time. Moreover, Corder achieves remarkable advantages in cross-platform scalability and reordering overhead.

PageRank, weighing the importance of vertices in a graph, serves as an fundamental algorithm for graph-structured tasks in a variety of domains. However, the processing capacity of multicore systems is oftentimes poorly utilized for large-scale PageRank due to the irregular memory accesses and poor cache efficiency. In this paper, we present HiPa, a novel hierarchical partitioning methodology to accelerate PageRank by utilizing the memory-cache architecture of the multicore system. For the shared memory, HiPa subdivides the graph based on the NUMA characteristics to reduce remote memory access while ensuring workload balance. For the private cache, HiPa further splits the graph into cache-able partitions to promote in-core computing and cache locality. Based on the partitioning strategy, systematical optimizations are proposed, such as thread management and new data layout. These effectively alleviate thread migration and thread contention, thus enhancing the scalability of HiPa. The integration of NUMA- and cache-aware parallelism allows HiPa to harness the potential of multicore systems. The performance of HiPa is evaluated by comparing with the the start-of-the-art graph frameworks and hand-optimized implementations. Over the best among them, HiPa achieves accelerations from 1.11 × to 1.45 × , and reductions in remote memory accesses from 1.87 × to 3.90 × . Moreover, we investigate the behaviors of HiPa on different processor micro-architectures to push its performance closer to hardware limit.

The intrinsic irregular data structure of graphs often causes poor cache utilization thus deteriorates the performance of graph analytics. Prior works have designed a variety of graph reordering methods to improve cache efficiency. However, little insight has been provided into the issue of workload imbalance for multicore systems. In this work, we identify that a major factor affecting the performance is the unevenly distributed computation load amongst cores. To cope with this problem, we propose cache-aware reordering (Corder), a lightweight reordering algorithm that facilitates workload balance as well as cache optimization. Comprehensive performance evaluation of Corder is conducted on various graph applications and datasets. We observe that Corder yields speedup of up to 2.59× (on average 1.47×) over original graphs.

Linux servers are being used in almost all clouds, datacenters and supercomputers today. Linux Kernel functions are facing a kind of malware attacks, known as rootkits with root-access capability. The rootkits appear asloadable kernel modules(LKM) in today's Linux servers. These modules hide from other kernel objects, and can redirect the kernel control flow by tampering with the metadata needed in kernel service functions. The kernel rootkits are invisible to users after loading, which may bypass most security shields. Both spatial and temporal appearance of rootkits are randomly distributed, which makes it difficult to detect or removal. To deal with rootkit threats, we propose a novelVirtual Wall(VTW) approach to filtering out the rootkit-embedded LKMs by tracing the incurred kernel activities. This VTW is essentially a lightweight hypervisor built with rootkit detection and event tracing capabilities. Normally, the Linux runs in a guest mode. When a LKM execution violates the security policy set by the VTW, the OS control will switch to a host mode. The VTW at host mode enables the detection and tracing of rootkit events timely. In other words, potential rootkit attacks are detected, traced and classified to make meaningful filtering decisions. The whole detection and tracing process is based on memory access control and event injection mechanisms. Experimental results show that the VTW defense system is effective to detect and defend against kernel rootkits timely. The CPU overhead for executing VTW is less than 2 percent. Compared with other defense schemes (such as DIKernel, etc.), our vs is easier to implement with low performance degradation on Linux servers. We will demonstrate the advantages of VTW through its simplicity in implementation and potential performance gains. We will also compare our system with seven other rootkit defense systems.

The increasing demand for machine learning computation contributes to the convergence of high-performance computing and cloud computing, in which the virtualization of Graphics Processing Units (GPUs) becomes a critical issue. Although many GPGPU virtualization frameworks have been proposed, their performance is limited by the bandwidth of data transactions between the virtual machine (VM) and host. In this paper, we present a virtualization framework, qCUDA, to improve the performance of compute unified device architecture (CUDA) programs. qCUDA is based on the virtio framework, providing the para-virtualized driver and the device module for performing the interaction with the API remoting and memory management methods. In our test environment, qCUDA can achieve above 95% of the bandwidth efficiency for most results by comparing it with the native. Also, qCUDA has the features of flexibility and interposition. It can execute CUDA-compatible programs in the Linux and Windows VMs, respectively, on QEMU-KVM hypervisor for GPGPU virtualization.

In the big data era, the distributed file system is getting more and more significant due to the characteristics of its scale-out capability, high availability, and high performance. Different distributed file systems may have different design goals. For example, some of them are designed to have good performance for small file operations, such as GlusterFS, while some of them are designed for large file operations, such as Hadoop distributed file system. With the divergence of big data applications, a distributed file system may provide good performance for some applications but fails for some other applications, that is, there has no universal distributed file system that can produce good performance for all applications. In this paper, we propose a hybrid file system framework, HybridFS, which can deliver satisfactory performance for all applications. HybridFS is composed of multiple distributed file systems with the integration of advantages of these distributed file systems. In HybridFS, on top of multiple distributed file systems, we have designed a metadata management server to perform three functions: file placement, partial metadata store, and dynamic file migration. The file placement is performed based on a decision tree. The partial metadata store is performed for files whose size is less than a few hundred Bytes to increase throughput. The dynamic file migration is performed to balance the storage usage of distributed file systems without throttling performance. We have implemented HybridFS in java on eight nodes and choose Ceph, HDFS, and GlusterFS as designated distributed file systems. The experimental results show that, in the best case, HybridFS can have up to 30% performance improvement of read/write operations over a single distributed file system. In addition, if the difference of storage usage among multiple distributed file systems is less than 40%, the performance of HybridFS is guaranteed, that is, no performance degradation.

Driven by the trends of BigData and Cloud computing, there is a growing demand for processing and analyzing data that are generated and stored across geo-distributed data centers. However, due to the limited network bandwidth between data centers and the growing data volume spread across different locations, it has become increasingly inefficient to aggregate data and to perform computations at a single data center. An approach that has been commonly used by data-intensive cluster computation systems, like Hadoop, is to distribute computations based on data locality so that data can be processed locally to reduce the network overhead and improve performance. But limited work has been done to adapt and evaluate such technique for geo-distributed data centers. In this paper, we proposed DRASH (Data-Replication Aware Scheduler), a job scheduling algorithm that enforces data locality to prevent data transfer, and exploits data replications to improve overall system performance. Our evaluation using simulations with realistic workload traces shows that DRASH can outperform other existing approaches by 16% to 60% in average job completion time, and achieve greater improvements under higher data replication factors.

The primary-copy consistency model used in Ceph cannot satisfy the low latency requirement of write operation required by users. In this paper, we propose a weak consistency model, PROAR, based on a distributed hash ring mechanism to allow clients to only commit data to the primary node and synchronize data to replication nodes asynchronously in Ceph. Based on the distributed hash ring mechanism, the low latency requirement of write operation can be met. In addition, the workload of the primary node can be reduced while that of replication nodes can be more balanced. We have evaluated the proposed scheme on a Ceph storage system with 3 storage nodes. The experimental results show that PROAR can reduce about 50% write overhead compared to that of Ceph and has a more balanced workload around all the replication nodes.

Heterogeneous System Architecture (HSA) is an archi-tecture developed by the HSA foundation aiming at reduc-ing programmability barriers as well as improving commu-nication efficiency for heterogeneous computing. For ex-ample, HSA allows heterogeneous computing devices to share the same virtual address space. This feature allows programmers to bypass explicit data copying between devices, as was required in the past. HSA features such as job dispatching through user level queues and memory based signaling help to reduce communication latency between the host and other computing devices. While the new features in HSA enable more efficient heterogeneous computing, they also introduce new chal-lenges to system virtualization, especially in memory virtu-alization and I/O virtualization. This work investigates the issues involved in HSA virtualization and implements a KVM-based hypervisor that supports the main features of HSA inside guest operating systems. Furthermore, this work shows that with the newly introduced hypervisor for HSA, system resources in HSA-compliant AMD Kaveri can be effectively shared between multiple guest operating sys-tems.

As the huge growth of mobile traffic amount, conventional Radio Access Networks (RANs) suffer from high capital and operating expenditures, especially when new cellular standards are deployed. Software, and cloud RANs have been proposed, but the stringent latency requirements e.g., 1 ms transmission time interval, dictated by cellular networks is difficult to satisfy. We first present a real software RAN testbed based on an opensource LTE implementation. We also investigate the issue of quality assurance when deploying such software RANs in cloud. In particular, running software RANs in cloud leads to high latency, which may violate the latency requirements. We empirically study the problem of minimizing computational and networking latencies in lightweight container cloud. Our experiment results show the feasibility of running software RANs in real-time container cloud. More specifically, a feasible solution to host software RANs in cloud is to adopt lightweight containers with real-time kernels and fast packet processing networking.

With the need of data storage increases tremendously nowadays, distributed file system becomes the most important data storage system in cloud computing. In distributed file system development, there are many researchers work hard to refine the architecture to provide scalability and reliability. In our work, we propose a distributed metaserver system including metaserver scale-out, metadata replication, metaserver recovery, and metaserver management recovery mechanisms. In our experiments, the proposed system can increase the capacity of metadata and increase the reliability by fault tolerance mechanism. The overhead of read/write data is very little in the proposed system as well.

Summary Constructing phylogenetic trees is of priority concern in computational biology, especially for developing biological taxonomies. As a conventional means of constructing phylogenetic trees, unweighted pair group method with arithmetic (UPGMA) is also an extensively adopted heuristic algorithm for constructing ultrametric trees (UT). Although the UT constructed by UPGMA is often not a true tree unless the molecular clock assumption holds, UT is still useful for the clocklike data. Moreover, UT has been successfully adopted in other problems, including orthologous‐domain classification and multiple sequence alignment. However, previous implementations of the UPGMA method have a limited ability to handle large taxa sets efficiently. This work describes a novel graphics processing unit (GPU)‐UPGMA approach, capable of providing rapid construction of extremely large datasets for biologists. Experimental results indicate that the proposed GPU‐UPGMA approach achieves an approximately 95× speedup ratio on NVIDIA Tesla C2050 GPU over the implementation with 2.13 GHz CPU. The developed techniques in GPU‐UPGMA also can be applied to solve the classification problem for large data set with more than tens of thousands items in the future.Copyright © 2014 John Wiley & Sons, Ltd.

This paper introduces a prototype of Taiwan UniCloud, a community-driven hybrid cloud platform for academics in Taiwan. The goal is to leverage resources in multiple clouds among different organizations. Each self-managing cloud can join the UniCloud platform to share its resources and simultaneously benefit from other clouds with scale-out capabilities. Accordingly, resources are elastic and sharable with each other such as to afford unexpected resource demands to each cloud. The proposed platform provides a web portal to operate each cloud via a uniform user interface. The construction of virtual clusters with multi-core VMs is supplied for parallel and distributed processing models. An object-based storage system is also delivered to federate different storage providers. This paper not only presents the architectural design of Taiwan UniCloud, but also evaluates the performance to demonstrate the possibility of current implementation. Experimental results show the feasibility of the proposed platform as well as the benefit from the cloud federation.

On behalf of the 20th IEEE International Conference on Parallel and Distributed Systems (ICPADS 2014) Organizing Committee, we are very pleased to announce that more than three hundred researchers and contributors from the world submitted their papers to share their research results and new ideas. The objective of this conference to provide a major international forum for scientists, engineers, and users to exchange and share their experiences, new ideas, and latest research results on all aspects of parallel and distributed computing systems.

In overlay‐based applications, multiple overlay networks are deployed to fulfill different service requirements. A multi‐overlay environment may exist in which a number of nodes simultaneously participate in the networks. When there are multiple overlay‐based applications running over a set of nodes, some of the nodes take extra effort to maintain multi‐overlay networks. Therefore, maintaining these co‐existing overlays incurs redundant maintenance overhead. This research presents a cooperative strategy for exploiting a master–slave model to handle the common overlay‐maintenance. The purpose is to eliminate the redundant maintenance overhead. To evaluate system performance, this study not only analyses various combinations of multiple overlays but also considers the effectiveness of the master selection approach. Experimental results demonstrated that the proposed cooperative strategy significantly decreases the redundant overlay‐maintenance overhead. In some cases, the overall reduction ratio of maintaining multiple overlays is as high as 60%.

Dynamic binary translation (DBT) is a core technologyto many important applications such as system virtualization, dynamic binary instrumentation, and security. However, there are several factors that often impede its performance: 1) emulation overhead before translation; 2) translation and optimization overhead; and 3) translated code quality. The issues also include its retargetabilitythat supports guest applications from different instruction-set architectures (ISAs) to host machines also with different ISAs-an important feature to system virtualization. In this work, we take advantage of the ubiquitous multicore platforms, and use a multithreaded approach to implement DBT. By running the translator and the dynamic binary optimizer on different cores with different threads, it could off-load the overhead incurred by DBT on the target applications; thus, afford DBT of more sophisticated optimization techniques as well as its retargetability. Using QEMU (a popular retargetable DBT for system virtualization) and Low-Level Virtual Machine (LLVM) as our building blocks, we demonstrated in a multithreaded DBT prototype, called Hybrid-QEMU (HQEMU), that it could improve QEMU performance by a factor of 2.6x and 4.1x on the SPEC CPU2006 integer and floating point benchmarks, respectively, for dynamic translation of x86 code to run on x86-64 platforms. For ARM codes to x86-64 platforms, HQEMU can gain a factor of 2.5x speedup over QEMU for the SPEC CPU2006 integer benchmarks. We also address the performance scalability issue of multithreaded applications across ISAs. We identify two major impediments to performance scalability in QEMU: 1) coarse-grained locks used to protect shared data structures, and 2) inefficient emulation of atomic instructions across ISAs. We proposed two techniques to mitigate those problems: 1) using indirect branch translation caching (IBTC) to avoid frequent accesses to locks, and 2) using lightweight memory transactions to emulate atomic instructions across ISAs. Our experimental results show that for multithread applications, HQEMU achieves 25X speedups over QEMU for the PARSEC benchmarks.

Barrier synchronization, an essential mechanism for a block of threads to guard data consistency, is regarded as a threat to performance. This study, however, provides a different viewpoint for barrier synchronization on GPUs: adding barrier synchronization, even when functionally unnecessary, can improve the performance of some memory-intensive applications. We explain this phenomenon using a memory contention model in which artificial barrier synchronization helps reduce memory contention and preserve data access locality. To yield practical applications, we identify a program pattern: artificial barrier synchronization can be used to synchronize the memory accesses when the data locality among threads is violated. Empirical results from three real-world applications demonstrate that artificial barrier synchronization can increase performance by 10 to 20 percent.

Big data refers to data that is so large that it exceeds the processing capabilities of traditional systems. Big data can be awkward to work and the storage, processing and analysis of big data can be problematic. MapReduce is a recent programming model that can handle big data. MapReduce achieves this by distributing the storage and processing of data amongst a large number of computers (nodes). However, this means the time required to process a MapReduce job is dependent on whichever node is last to complete a task. This problem is exacerbated by heterogeneous environments. In this paper we propose a method to improve MapReduce execution in heterogeneous environments. This is done by dynamically partitioning data during the Map phase and by using virtual machine mapping in the Reduce phase in order to maximize resource utilization.

The Dalvik virtual machine is the main application platform running on Google's Android operating system for mobile devices and tablets. It is a Java Virtual Machine running a basic trace-based JIT compiler, unlike web browser JavaScript engines that usually run a combination of both method and trace-based JIT types. We developed a method-based JIT compiler based on the Low Level Virtual Machine framework that delivers performance improvement comparable to that of an Ahead-Of-Time compiler. We compared our method-based JIT against Dalvik's own trace-based JIT using common benchmarks available in the Android Market. Our results show that our method-based JIT is better than a basic trace-based JIT, and that, by sharing profiling and compilation information among each other, a smart combination of both JIT techniques can achieve a great performance gain.

As the computational power of Graphics Processing Unit (GPU) increases, data transmission becomes the major performance bottleneck. In this study, we investigate two techniques, data streaming and data compression, to reduce the communication cost on GPU. Data streaming enables overlap of communication and computation, whereas data compression reduces the data size transferred among different memory spaces. Although both techniques increase computation cost, overall performance can still be enhanced by reducing communication cost. We demonstrate the effectiveness of the two techniques via two case studies: radix sort and 3-star, a deployment algorithm in wireless sensor networks. For radix sort, a new algorithm, which mixes MSD and LSD algorithms and employs data streaming, is presented. Its performance is 25% faster than the fastest GPU radix sort implementation currently available in the public domain. For the 3-star algorithm, the speed increases several hundreds of times faster than that obtained by the CPU code. The data streaming and data compression, which is a hybrid CPU-GPU algorithm, provide an additional 54% performance improvement to the GPU implementation. Data compression not only reduces communication cost, but also improves the computation time, by which further performance enhancement can be achieved.

Dynamic binary translation (DBT) is a core technology to many important applications such as system virtualization, dynamic binary instrumentation and security. However, there are several factors that often impede its performance: (1) emulation overhead before translation; (2) translation and optimization overhead, and (3) translated code quality. On the dynamic binary translator itself, the issues also include its retargetability to support guest applications from different instruction-set architectures (ISAs) to host machines also with different ISAs, an important feature for system virtualization. In this work, we take advantage of the ubiquitous multicore platforms, using multithreaded approach to implement DBT. By running the translators and the dynamic binary optimizers on different threads on different cores, it could off-load the overhead caused by DBT on the target applications; thus, afford DBT of more sophisticated optimization techniques as well as the support of its retargetability. Using QEMU (a popular retargetable DBT for system virtualization) and LLVM (Low Level Virtual Machine) as our building blocks, we demonstrated in a multi-threaded DBT prototype, called HQEMU, that it could improve QEMU performance by a factor of 2.4X and 4X on the SPEC 2006 integer and floating point benchmarks for x86 to x86-64 emulations, respectively, i.e. it is only 2.5X and 2.1X slower than native execution of the same benchmarks on x86-64, as opposed to 6X and 8.4X slowdown on QEMU. For ARM to x86-64 emulation, HQEMU could gain a factor of 2.4X speedup over QEMU for the SPEC 2006 integer benchmarks.

Multiple sequence alignments with constrains has become an important problem in the computational biology. The concept of constrained sequence alignment is proposed to incorporate the biologist's domain knowledge into sequence alignments such that the user-specified residues/segments are aligned together in the alignment results. Over the past decade, a series of constrained multiple sequence alignment tools were proposed in the literature. GPU-REMuSiC is a newest tool with the regular expression constrains and uses the graphics processing units (GPUs) with CUDA. GPU-REMuSiC can achieve 29× speedups for overall computation time by the experimental results. However, the execution environment of GPU-REMuSiC need to build, and it's a threshold for biologists to set up. Therefore, we design an intuitive friendly user interface for the potential cloud server with GPUs. Use the user interface through network, we can send the input data to remote server without cumbersome setting in local host. Finally, we can receive the alignment results from the remote cloud server with GPUs.

With the ability to provide on-demand service and to reduce the IT cost, cloud computing becomes more and more popular recently. Virtualization is one of the important technologies in cloud computing, whose main idea is to provide abstractions of the physical resources. However, such abstraction can cause performance degradation, especially for I/O virtualization, which is usually the performance bottleneck in cloud computing. InfiniBand is a network system that provides very low latency (less than 5us) and very high bandwidth (multiple Gbps). Due to its excellent performance, InfiniBand is commonly used in high performance computing (HPC) area. In this paper, we propose Virt-IB for InfiniBand virtualization on Kernel-based Virtual Machine (KVM). The main components of Virt-IB are VM IB library and Virt-IB driver. Our design processes InfiniBand APIs directly in guest VM and communicates with InfiniBand device indirectly to perform the real operations. VM IB library provides API interface and user-level InfiniBand driver. Virt-IB driver provides a channel for VM IB library to write commands into InfiniBand device indirectly. Evaluation results show that our current work is better than network virtualization and it can achieve about 50% performance of native InfiniBand.

As the scale of datacenter continues to grow, it is hard to keep servers homogenous, with the same hardware and performance characteristics. Today's datacenters commonly operates on several generations of servers from multiple vendors, and mix both high-end and low-end devices together to deliver service quality requirement with lowest cost. However, the heterogenous environment also complicates the management of the datacenters, especially in terms of resource allocation. In this paper, we focus on the resource allocation of a tightly unified block-level storage with SSD and HDD. We conduct experiments to quantify the performance of difference access patterns on each type storage devices. Then formulate our resource allocation problem into a ILP (Integer Linear Programming), and proposed data migration algorithms based on the observations. We evaluate our solution by implementing a heterogenous storage consist of HDD, SDD and iSCSI HDD, and show the data access response time can be reduced by 27%.

TurboVG is a hardware accelerator for the OpenVG 1.1 library that operates sixteen times faster than an optimized software implementation. This improved efficiency stems from a well-designed hardware-software interaction capable of handling massive data transfers across hierarchical layers without performance loss. By combining multiple TurboVG cores, the library can support screen resolutions of up to Full-HD 1080p.

The execution environment of Android system is based on a virtual machine called Dalvik virtual machine (DVM) in which the execution of an application program is in interpret-mode. To reduce the interpretation overhead of DVM, Google has included a trace-based just-in-time compiler (JITC) in the latest version of Android. Due to limited resources and the requirement for reasonable response time, the JITC is unable to apply deep optimizations to generate high quality code. In this paper, we propose a method-based ahead-of-time compiler (AOTC), called Icing, to speed up the execution of Android applications without the modification of any components of Android framework. The main idea of Icing is to convert the hot methods of an application program from DEX code to C code and uses the GCC compiler to translate the C code to the corresponding native code. With the Java Native Interface (JNI) library, the translated native code can be called by DVM. Both AOTC and JITC have their strength and weakness. In order to combine the strength and avoid the weakness of AOTC and JITC, in Icing, we have proposed a cost model to determine whether a method should be handled by AOTC or JITC during profiling. To evaluate the performance of Icing, four benchmarks used by Google JITC are used as test cases. The performance results show that, with Icing, the execution time of an application is two to three times faster than that without JITC, and 25% to 110% faster than that with JITC.

In this paper, we investigate efficient algorithms and implementations using GPU plus CPU to solve the rectangle intersection problem on a plane. The problem is to report all intersecting pairs of iso-oriented rectangles, whose parallelization on GPUs poses two major computational challenges: data partition and the massive output. The algorithm we presented is called PRI-GC, Parallel Rectangle Intersection algorithm on GPU+CPU, which consists of two phases: mapping and intersection-checking. In the mapping phase, rectangles are hashed into different subspaces (called cells) to reduce the unnecessary intersection checking for far-apart rectangles. In the intersection-checking phase, pairs of rectangles within the same cell are examined in parallel, and the intersecting pairs of rectangles are reported. Several optimization techniques, including rectangles re-ordering, output data compressing/encoding, and the execution overlapping of GPU and CPU, are applied to enhance the performance. We had evaluated the performance of PRI-GC and the result shows over 30x speedup against two well-implemented sequential algorithms on single CPU. The effectiveness of each optimization technique for this problem was evaluated as well. Several parameters, including different degrees of rectangle coverage, different block sizes, and different cell sizes, were also experimented to explore their influences on the performance of PRI-GC.

This paper proposes a processor allocation technique named temporal look-ahead processor allocation (TLPA) that makes allocation decision by evaluating the allocation effects on subsequent jobs in the waiting queue. TLPA has two strengths. First, it takes multiple performance factors into account when making allocation decision. Second, it can be used to optimize different performance metrics. To evaluate the performance of TLPA, we compare TLPA with best-fit and fastest-first algorithms. Simulation results show that TLPA has up to 32.75% performance improvement over conventional processor allocation algorithms in terms of average turnaround time in various system configurations.

Communication-aware task mapping algorithms, which map parallel tasks onto processing nodes according to the communication patterns of applications, are essential to reduce the communication time in modern high performance computing. In this paper, we design algorithms specifically for interconnected multicore systems, whose architectural property, namely small number of cores per node, large number of nodes, and large performance gap between the communication within a multicore and among multicores, had brought new challenges and opportunities to the mapping problem. Let k be the number of cores per multicore and n be the number of tasks. We consider the practical case that k ≪ n for k = 2,4, and 6. The designed algorithms are optimal for the mapping measurement, called Maximum Interconnective Message Size (MIMS), and of time complexity merely O(m log m) for m communication pairs. Thus, they are highly scalable for large applications. We had experimented the algorithms on the IBM Blue Gene/P system for two synthetic benchmarks and two applications. The results show good communication performance improvement.

A full system emulator, such as QEMU, can provide a versatile virtual platform for software development. However, most current system simulators do not have sufficient support for multi-processor emulations to effectively utilize the underlying parallelism presented by today's multi-core processors. In this paper, we focus on parallelizing a system emulator and implement a prototype parallel emulator based on the widely used QEMU. Using this parallel QEMU, emulating an ARM11MPCore platform on a quad-core Intel i7 machine with the SPLASH-2 benchmarks, we have achieved 3.8x speedup over the original QEMU design. We have also evaluated and compared the performance impact of two different parallelization strategies, one with minimum sharing among emulated CPU, and one with maximum sharing.

The ubiquity of many-core architectures brings challenges in making scalable application software, changing dramatically from the way applications are traditionally developed. Optimization of programs for many-core platforms is a multifaceted problem, where system and architectural factors should be taken into consideration. In this paper, we attack the problem on the aspect of programming paradigm. We propose a hybrid producer-write plus consumer-read shared-memory programming paradigm for implementation of a master-worker video decoder on the TILE64 many-core platform. To evaluate the scalability and performance benefits of different programming paradigms, a Motion JPEG decoder is parallelized using master-worker structure and implemented with combinations of consumer-read programming and producer-write programming. Experimental results show that the proposed implementation obtained competitive performance speedup, scaling well with number of available cores and up to 4 times performance improvement over other implementations on the decoding of a 1080P video.

Overlay networks are widely adopted in many distributed systems for efficient resource sharing. Recently, issues in overlay network have also been introduced into cloud systems, in order to organize thousands of virtualized resources. In parallel, the explosion of P2P applications introduces the multi-overlay environment in which a number of nodes simultaneously participate in multiple overlays. When multiple applications running over a large set of nodes, some of nodes may take repeated efforts to preserve multi-overlay networks. Therefore, maintaining these co-existing overlays brings the redundant maintenance overhead. This paper presents a cooperative strategy to analyze the overlay maintenance of multi-overlay environments and to elaborate multiple overlays for simplifying the overlay maintenance. The proposed strategy exploits the synergy of co-existing overlays to handle their common overlay-maintenance, so that the redundant maintenance overhead could be eliminated while keeping performance. To evaluate the system performance, this paper not only analyzes several overlays but also considers realistic multi-overlay environments by varying the intersection ratio of diverse overlays and the combination of multiple overlays. Experimental results show that the proposed cooperative strategy significantly decreases the redundant overlay-maintenance overhead, where the reduction ratio of maintaining multiple overlays is higher than 60 percent in some of cases.

This work is to augment a debris flow observation and early warning system with wireless sensor networks. Previously, the GIS at Fengchia University has constructed and deployed state-of-the-art, stationary and mobile types of observation systems at nearly 20 sites throughout Taiwan. These sites collect data from sensors ranging from rain gauges and tension cables to ultrasonic sensors and CCD cameras, and transmit them back to the GIS via a lower-orbit satellite uplink in real-time. A new wireless sensor network and middleware system are being designed and implemented to overcome several limitations with the current system. Wireless communication capabilities are being incorporated to enhance the coverage. Previously, most connections between the sensors and the server before the satellite uplink are wired or Wi-Fi with fixed topology and limited range. New wireless interfaces with a 500 m - 1 km range plus energy harvesting devices on the sensors reduces deployment effort and cost. More importantly, it is now becoming possible to construct and deploy brand new types of mobile sensor nodes that move with the debris flow along its path. Such sensor nodes are to be housed in pyramid-shaped, weather-proof capsules that contain motion sensors, GPS and other localization devices, energy harvesting and storage devices, and wireless transceivers. Normally in low-power or standby mode, these capsules would be deployed in the path of potential debris flows. They would stand steadily during normal weather conditions including wind, rain, and water flow. They would get triggered by a threshold motion detector or a rain gauge and start actively monitoring the flow. As it flows with the debris, these capsules transmit their sensor data wirelessly, via other relaying nodes if necessary. Based on the shape and mass of the capsule itself and the velocity, researchers can derive the direction and magnitude of the flow in brand new ways.

Sequence alignment is a fundamental problem in the computational biology. Many alignment methods have been proposed in the literature, such as pair-wise sequence alignment (2SA), syntenic alignment, multiple sequence alignment (MSA) and constraint multiple sequence alignment, etc. Three-sequence alignment (3SA) problem has been proposed and discussed in the computational biology and proved that the alignment results from 3SA are better than those from 2SA under some conditions. However, 3SA problem is less discussed over the past decade due to the computer capability. 3SA problem now is worthy to discuss due to the powerful computer and more and more genome and protein sequences. In this paper, an efficient parallel algorithm (P3SA) is proposed to solve 3SA problem. The P3SA method requires 0(n2/p) space complexity and 0(n3/p) time complexity. The experimental results show that P3SA algorithm is applicable and achieves a satisfied speed-up.

In this paper, we present a heuristic algorithm that improves the performance of static task scheduling. Our algorithm is based on the list-scheduling mechanism. For the listing phase, we use existing techniques to generate partial-order task sequences based on critical-path-first ordering, critical-task-first ordering, and their hybrids. For the scheduling phase, we propose a task-duplication algorithm with a look-ahead technique, so that the complexity of the new algorithm does not increase. The experiment results show that our algorithm outperforms other algorithms for any feasible task sequences with respect to the average execution times and the average scheduling length ratios.

In this paper, we propose a general turn model, Tree-turn model, for irregular topology. In Tree-turn model, links are classified as either tree or cross and six directions are associated with channels of links. From these six directions, we prohibit some turns such that an efficient deadlock-free routing algorithm, Tree-turn routing, can be derived. There are three phases to construct the Tree-turn routing. First, build up a coordinated tree for a given topology. Second, construct a communication graph of the topology and the corresponding coordinated tree. Third, set up the forwarding table by using the all-pairs shortest path algorithm according to the prohibited turns derived from the Tree-turn model and the directions of the channels in communication graph. To evaluate the performance, we implement the Tree-turn routing algorithm along with the up*/down* routing algorithm and the L-turn routing algorithm on a software simulator. The simulation results show that Tree-turn routing outperforms other two routing algorithms for all test cases

The multicast operation is a very commonly used operation in parallel applications. With the hardware supported multicast of the InfiniBand architecture (IBA), we propose a cyclic multicast scheme for fat-tree-based (m-port n-tree) InfiniBand networks. The basic concept of the proposed cyclic multicast scheme is to find the union sets of the output ports of switches in the paths between the source processing node and each destination processing node in a multicast group. Based on the union sets and the path selection scheme, the forwarding table for a given multicast group can be constructed. We implement the proposed multicast scheme along with the OpenSM multicast scheme and the unicast scheme on an m-port n-tree InfiniBand network simulator. The simulation results show that the proposed multicast scheme outperforms the unicast scheme for all simulated cases. For many-to-many and all-to-many cases, the cyclic multicast scheme outperforms the OpenSM multicast scheme. For many-to-all case, the performance of the cyclic multicast scheme is a little better than that of the OpenSM multicast scheme

We proposed an efficient deadlock-free tree-based routing algorithm, the DOWN/UP routing, for irregular wormhole-routed networks based on the turn model. In a tree-based routing algorithm, hot spots around the root of a spanning tree and the uneven traffic distribution are the two main facts degrade the performance of the routing algorithm. To solve the hot spot and the uneven traffic distribution problems, in the DOWN/UP routing, it tries to push the traffic downward to the leaves of a spanning tree as much as possible and remove prohibited turn pairs with opposite directions in each node, respectively. To evaluate the performance of DOWN/UP routing, the simulation is conducted. We have implemented the DOWN/UP routing along with the L-turn routing on the IRFlexSim0.5 simulator. Irregular networks that contain 128 switches with 4-port and 8-port configurations are simulated. The simulation results show that the proposed routing algorithm outperforms the L-turn routing for all test samples in terms of the degree of hot spots, the traffic load distribution, and throughput.

Summary form only given. In a cluster system, performance of the interconnection network greatly affects the computation power generated together from all interconnected processing nodes. The network architecture, the interconnection topology, and the routing scheme are three key elements dominating the performance of an interconnection network. InfiniBand architecture (IBA) is a new industry standard architecture. It defines a high-bandwidth, high-speed, and low-latency message switching network that is good for constructing high-speed interconnection networks for cluster systems. Fat-trees are well-adopted as the topologies of interconnection networks because of many nice properties they have. We proposed an m-port n-tree approach to construct fat-tree-based InfiniBand networks. Based on the constructed fat-tree-based InfiniBand networks, we proposed an efficient multiple LID (MLID) routing scheme. The proposed routing scheme is composed of processing node addressing scheme, path selection scheme, and forwarding table assignment scheme. To evaluate the performance of the proposed routing scheme, we have developed a software simulator for InfiniBand networks. The simulation results show that the proposed routing scheme runs well on the constructed fat-tree-based InfiniBand networks and is able to efficiently utilize the bandwidth and the multiple paths that fat-tree topology offers under InfiniBand architecture.

We have proposed the extended Karnaugh map representation (EKMH) scheme for multidimensional array representation. We propose two data compression schemes, EKMR compressed row/column storage (ECRS/ECCS), for multidimensional sparse arrays based on the EKMR scheme. To evaluate the proposed schemes, we compare them to the CRS/CCS schemes. Both theoretical analysis and experimental tests were conducted. In the theoretical analysis, we analyze the CRS/CCS and the ECRS/ECCS schemes in terms of the time complexity, the space complexity, and the range of their usability for practical applications. In experimental tests, we compare the compressing time of sparse arrays and the execution time of matrix-matrix addition and matrix-matrix multiplication based on the CRS/CCS and the ECRS/ECCS schemes. The theoretical analysis and experimental results show that the ECRS/ECCS schemes are superior to the CRS/CCS schemes for all the evaluated criteria, except the space complexity in some case.

Array operations are useful in a large number of important scientific codes, such as molecular dynamics, finite element methods, climate modeling, atmosphere and ocean sciences, etc. In our previous work, we have proposed a scheme of extended Karnaugh map representation (EKMR) for multidimensional array representation. We have shown that sequential multidimensional array operation algorithms based on the EKMR scheme have better performance than those based on the traditional matrix representation (TMR) scheme. Since parallel multidimensional array operations have been an extensively investigated problem, we present efficient data parallel algorithms for multidimensional array operations based on the EKMR scheme for distributed memory multicomputers. In a data parallel programming paradigm, in general, we distribute array elements to processors based on various distribution schemes, do local computation in each processor, and collect computation results from each processor. Based on the row, column, and 2D mesh distribution schemes, we design data parallel algorithms for matrix-matrix addition and matrix-matrix multiplication array operations in both TMR and EKMR schemes for multidimensional arrays. We also design data parallel algorithms for six Fortran 90 array intrinsic functions: All, Maxval, Merge, Pack, Sum, and Cshift. We compare the time of the data distribution, the local computation, and the result collection phases of these array operations based on the TMR and the EKMR schemes. The experimental results show that algorithms based on the EKMR scheme outperform those based on the TMR scheme for all test cases.

Software standards are highly recommended because they promise faster and more efficient ways for software development with proven techniques and standard notations. Designers who adopt standards like UML and design patterns to construct models and designs in the processes of development suffer from a lack of communication and integration of various models and designs. Also, the problem of implicit inconsistency caused by making changes to components of the models and designs will significantly increase the cost and error for the process of maintenance. In this paper, an XML-based unified model is proposed to solve the problems and to improve both software development and maintenance through unification and integration.

For sparse array operations, in general, the sparse arrays are compressed by some data compression schemes in order to obtain better performance. The Compressed Row/Column Storage (CRS/CCS) schemes are the two common used data compression schemes for sparse arrays in the traditional matrix representation (TMR). When extended to higher dimensional sparse arrays, array operations using the CRS/CCS schemes usually do not perform well. We propose two data compression schemes, extended Karnaugh map representation Compressed Row/Column Storage (ECRS/ ECCS) for multi-dimensional sparse arrays based on the EKMR scheme. To evaluate the proposed schemes, both theoretical analysis and experimental tests are conducted. In theoretical analysis, we analyze CRS/CCS and ECRS/ECCS schemes in terms of the time complexity, the space complexity, and the range of their usability for practical applications. In experimental test, we compare the performance of matrix-matrix addition and matrix-matrix multiplication sparse array operations that use the CRS/CCS and ECRS/ECCS schemes. The experimental results show that sparse array operations based on the ECRS/ECCS schemes outperform those based on the CRS/CCS schemes for all test samples.

In this paper we present an efficient data compression scheme, the template run-length encoding (TRLE) scheme, for image composition of parallel volume rendering systems. Given an image with 2n/spl times/2n pixels, in the TRLE scheme, the image is treated as n/spl times/n blocks and each block has 2/spl times/2 pixels. Since a pixel can be a blank or non-blank pixel, there are 16 templates in a block. To compress an image, the TRLE scheme uses the templates to encode blocks row by row. Blocks in the same row are encoded as a TRLE-sequence. By packing all TRLE-sequences in a packet, the packet is the compressed partial image that can be sent/received among processors. To evaluate the performance of the TRLE scheme, we compare the proposed scheme with the BR, the RLE, and the BRLC schemes. Since a data compression scheme needs to cooperate with some data communication schemes, in the implementation, the binary-swap (BS), the parallel-pipelined (PP), and the rotate-tiling (RT) data communication schemes are used. By combining the four data compression schemes with the three data communication schemes, we have twelve image composition methods. These twelve methods are implemented on a PC cluster The data computation time and the data communication time are measured. The experimental results show that the TRLE data compression scheme with the RT data communication scheme outperforms other eleven image composition methods.

Array operations are used in a large number of important scientific codes. To implement these array operations efficiently, many methods have been proposed in the literature, most of which are focused on two-dimensional arrays. When extended to higher dimensional arrays, these methods usually do not perform well. Hence, designing efficient algorithms for multidimensional array operations becomes an important issue. We propose a new scheme, extended Karnaugh map representation (EKMR), for the multidimensional array representation. The main idea of the EKMR scheme is to represent a multidimensional array by a set of two-dimensional arrays. Hence, efficient algorithm design for multidimensional array operations becomes less complicated. To evaluate the proposed scheme, we design efficient algorithms for multidimensional array operations, matrix-matrix addition/subtraction and matrix-matrix multiplications, based on the EKMR and the traditional matrix representation (TMR) schemes. Theoretical and experimental tests for these array operations were conducted. In the experimental test, we compare the performance of intrinsic functions provided by the Fortran 90 compiler with those based on the EKMR scheme. The experimental results show that the algorithms based on the EKMR scheme outperform those based on the TMR scheme and those provided by the Fortran 90 compiler.

The marching cubes method is a well-known surface extraction method by using the surface configurations of cubes for surface rendering of volume data. The marching cubes method has three main disadvantages: it is time consuming, ambiguous, and holes are generated. All these disadvantages come from the use of the surface configurations of cubes. We propose an efficient surface extraction method, the marching voxels method, for surface rendering of volume data. Instead of using the surface configurations of cubes, the marching voxels method first generates triangles for inner voxels. Then it combines the triangles of inner voxels to produce the surface of an object. Finally, the surface of an object is projected to a plane to form the final image. Since the marching voxels method considers the combination of triangles of voxels not cubes and the combination of triangles is performed in a deterministic way, there is neither ambiguous case of a combination nor holes for the generated surface. The experimental results show that the marching voxels method saves about 30% of the surface rendering time compared to the marching cubes method for test samples.

The association rule mining can be divided into two steps. The first step is to find out all frequent itemsets, whose occurrences are greater than or equal to the user-specified threshold. The second step is to generate reliable association rules based on all frequent itemsets found in the first step. Identifying all frequent itemsets in a large database dominates the overall performance in the association rule mining. In this paper, we propose an efficient hash-based method, HMFS, for discovering the maximal frequent itemsets. The HMFS method combines the advantages of both the DHP (Direct Hashing and Pruning) and the Pincer-Search algorithms. The combination leads to two advantages. First, the HMFS method, in general, can reduce the number of database scans. Second, the HMFS can filter the infrequent candidate itemsets and can use the filtered itemsets to find the maximal frequent itemsets. These two advantages can reduce the overall computing time of finding the maximal frequent itemsets. In addition, the HMFS method also provides an efficient mechanism to construct the maximal frequent candidate itemsets to reduce the search space. We have implemented the HMFS method along with the DHP and the Pincer-Search algorithms on a Pentium III 800 MHz PC. The experimental results show that the HMFS method has better performance than the DHP and the Pincer-Search algorithms for most of test cases. In particular, our method has significant improvement over the DHP and the Pincer-Search algorithms when the size of a database is large and the length of the longest itemset is relatively long.

In this paper we use the tensor product notation as the framework of a programming methodology for designing various parallel prefix algorithms. In this methodology, we first express a computational problem in its matrix form. Next, we formulate a matrix equation for the matrix of the computational problem. Then, solve the matrix equation to obtain some simple matrices. Finally, we recursively factorize the subproblem to obtain a tensor product formula representing an algorithm for this problem. We will use the parallel prefix computation problem to illustrate our methodology and derive various parallel prefix algorithms including divide-and-conquer and recursive doubling algorithms.

The binary-swap and the parallel-pipelined methods are two popular image composition methods for volume rendering on distributed memory multicomputers. However, these methods either restrict the number of processors to a power of two or require many steps to transform image data that results in high communication overheads. In this paper, we present an efficient image composition method, the rotate-tiling (RT), for parallel volume rendering on distributed memory multicomputers. The RT method can fully utilize all available processors and minimize the communication overheads. In addition, we provide data compression method, the template run-length encoding (TRLE), to further reduce the communication data size. To evaluate the performance of the RT method, we compare the proposed method with the binary-swap method and the parallel-pipelined method. Both theoretical analysis and experimental test are conducted. In the theoretical analysis, we analyze the best performance bound of the RT method in terms of the startup time, the data transmission time, the number of processors, and the number of initial block of a sub-image. In the experimental test, we have implemented these three methods on an SP2 parallel machine. Three volume datasets are used as test samples. The experimental results show that our method outperforms the binary-swap and the parallel-pipelined methods for all test samples and match the results analyzed in the theoretical analysis. For the TRLE method, the experimental results show that the TRLE method can further reduce the composition time for these three methods.

In many scientific applications, array redistribution is usually required to enhance data locality and reduce remote memory access in many parallel programs on distributed memory multicomputers. Since the redistribution is performed at runtime, there is a performance trade-off between the efficiency of the new data decomposition for a subsequent phase of an algorithm and the cost of redistributing data among processors. In this paper, we present a generalized processor mapping technique to minimize the amount of data exchange for BLOCK-CYCLIC(kr) to BLOCK-CYCLIC(r) array redistribution and vice versa. The main idea of the generalized processor mapping technique is first to develop mapping functions for computing a new rank of each destination processor. Based on the mapping functions, a new logical sequence of destination processors can be derived. The new logical processor sequence is then used to minimize the amount of data exchange in a redistribution. The generalized processor mapping technique can handle array redistribution with arbitrary source and destination processor sets and can be applied to multidimensional array redistribution. We present a theoretical model to analyze the performance improvement of the generalized processor mapping technique. To evaluate the performance of the proposed technique, we have implemented the generalized processor mapping technique on an IBM SP2 parallel machine. The experimental results show that the generalized processor mapping technique can provide performance improvement over a wide range of redistribution problems.

The finite element method is widely applied to many domains, such as engineering, atmology, oceanography, biology, etc. The major drawback of the finite element method is that its execution takes a lot of time and memory spaces. Due to the computation-intensiveness and computation-locality properties, we can use the parallel processing method to improve the performance of the finite element method on distributed memory computing environments. However, it is quite difficult to program the finite element method on a distributed memory computing environment. Therefore, the development of a front-end parallel partial differential equations solver generation system is important. In this paper, we want to develop a front-end parallel partial differential equations solver generation system based on the World Wide Web on a distributed-memory computing environment, such as a PC cluster, a workstation cluster, etc. With the system, users who want to use parallel computers to solver partial differential equations can use web browser to input data and parameters. The system will automatically generate the corresponding parallel codes and execute the codes on the distributed memory computing environment. The execution result will be shown on the web browser. The results can also be download by user.

In many scientific applications, dynamic array redistribution is usually required to enhance the performance of an algorithm. In this paper, we present a generalized basic-cycle calculation (GBCC) method to efficiently perform a BLOCK-CYCLIC(s) over P processors to BLOCK-CYCLIC(t) over Q processors array redistribution. In the GBCC method, a processor first computes the source/destination processor/data sets of array elements in the first generalized basic-cycle of the local array it owns. A generalized basic-cycle is defined as lcm(sP, tQ)/(gcd(s,t)/spl times/P) in the source distribution and lcm(sP, tQ)/(gcd(s,t)/spl times/Q) in the destination distribution. From the source/destination processor/data sets of array elements in the first generalized basic-cycle, we can construct packing/unpacking pattern tables to minimize the data-movement operations. Since each generalized basic-cycle has the same communication pattern, based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the GBCC method, we have implemented this method on an IBM SP2 parallel machine, along with the PITFALLS method and the ScaLAPACK method. The cost models for these three methods are also presented. The experimental results show that the GBCC method outperforms the PITFALLS method and the ScaLAPACK method for all test samples. A brief description of the extension of the GBCC method to multidimensional array redistributions is also presented.

In the sort-last-sparse parallel volume rendering system on distributed memory multicomputers, as the number of processors increases, in the rendering phase, we can get a good speedup because each processor renders images locally without communicating with other processors. However, in the compositing phase, a processor has to exchange local images with other processors. When the number of processors is over a threshold, the image compositing time becomes a bottleneck. In this paper, we proposed three compositing methods, the binary-swap with bounding rectangle method, the binary-swap with run-length encoding and static load-balancing method, and the binary-swap with bounding rectangle and run-length encoding method, to efficiently reduce the compositing time in the sort-last-sparse parallel volume rendering system on distributed memory multicomputers. The proposed methods were implemented on an SP2 parallel machine along with the binary-swap compositing method. The experimental results show that the binary-swap with bounding rectangle and run-length encoding method has the best performance among the four methods.

To solve the load imbalance problem of a solution-adaptive finite element application program on a distributed memory multicomputer, nodes of a refined finite element graph can be remapped to processors or load of a refined finite element graph can be redistributed based on the current load of each processor. For the former case, remapping can be performed by some fast mapping algorithms. For the latter case, a load-balancing algorithm can be applied to balance the computational load of each processor. In this paper, three tree-based parallel load-balancing methods, the MCSTLB method, the BTLB method, and the CBTLB method, were proposed to deal with the load imbalance problems of solution-adaptive finite element application programs. To evaluate the performance of the proposed methods, we have implemented those methods along with three mapping methods, the AE/ORB method, the AE/MC method, and the MLkP method, on an SP2 parallel machine. Three criteria, the execution time of mapping/load-balancing methods, the execution time of a solution-adaptive finite element application program under different mapping/load-balancing methods, and the speedups achieved by mapping/load-balancing methods for a solution-adaptive finite element application program, are used for the performance evaluation. The experimental results show that 1) if the initial mapping is performed by a mapping method and the same mapping method and load-balancing methods were used in each refinement to balance the load of processors, the execution time of an application program under a load-balancing method is always shorter than that of the mapping method, and 2) the execution time of an application program under the CBTLB method is shorter than that of the BTLB method and the MCSTLB method.

In many scientific applications, dynamic array redistribution is usually required to enhance the performance of an algorithm. We present a generalized basic cycle calculation (GBCC) method to efficiently perform a BLOCK-CYCLIC(s) over P processors to BLOCK-CYCLIC(t) over Q processors array redistribution. In the GBCC method, a processor first computes the source/destination processor/data sets of array elements in the first generalized basic cycle of the local array it owns. A generalized basic cycle is defined as lcm(sP,tQ)/(gcd(s,t)/spl times/P) in the source distribution and lcm(sP,tQ)/(gcd(s,t)/spl times/Q) in the destination distribution. From the source/destination processor/data sets of array elements in the first generalized basic cycle, we can construct packing/unpacking pattern tables. Based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the GBCC method, we have implemented this method on an IBM SP2 parallel machine, along with the PITFALLS method and the ScaLAPACK method. The cost models for these three methods are also presented. The experimental results show that the GBCC method outperforms the PITFALLS method and the ScaLAPACK method for all test samples. A brief description of the extension of the GBCC method to multi dimensional array redistributions is also presented.

In this paper, we propose a prefix code matching parallel load-balancing method (PCMPLB) to efficiently deal with the load unbalancing problems of solution-adaptive finite element application programs on distributed memory multicomputers. The main idea of the PCMPLB method is first to construct a prefix code tree for processors. Based on the prefix code tree, a schedule for performing load transfer among processors can be determined by concurrently and recursively dividing the tree into two subtrees and finding a maximum matching for processors in the two subtrees until the leaves of the prefix code tree are reached. The experimental results show that the execution time of an application program under the PCMPLB method is less than that of the direct diffusion method and the multilevel diffusion method.

Array redistribution is usually required to enhance algorithm performance in many parallel programs on distributed memory multicomputers. Since it is performed at run-time, there is a performance trade-off between the efficiency of the new data decomposition for a subsequent phase of an algorithm and the cost of redistributing data among processors. In this paper, we present a basic-cycle calculation technique to efficiently perform BLOCK-CYCLIC(S) to BLOCK-CYCLIC(t) redistribution. The main idea of the basic-cycle calculation technique is, first, to develop closed forms for computing source/destination processors of some specific array elements in a basic-cycle, which is defined as icm(s,t)/gcd(s,t). These closed forms are then used to efficiently determine the communication sets of a basic-cycle. From the source/destination processor/data sets of a basic-cycle, we can efficiently perform a BLOCK-CYCLIC(s) to BLOCK-CYCLIC(t) redistribution. To evaluate the performance of the basic-cycle calculation technique, we have implemented this technique on an IBM SP2 parallel machine, along with the PITFALLS method and the multiphase method. The cost models for these three methods are also presented. The experimental results show that the basic-cycle calculation technique outperforms the PITFALLS method and the multiphase method for most test samples.

Array redistribution is usually required to enhance algorithm performance in many parallel programs on distributed memory multicomputers. Since it is performed at run-time, there is performance tradeoff between the efficiency of new data decomposition for a subsequent phase of an algorithm and the cost of redistributing data among processors. We present efficient algorithms for array redistribution. The most significant improvement of our algorithms is that a processor does not need to construct the send/receive data sets for a redistribution. Based on the packing/unpacking information that derived from the BLOCK-CYCLIC(kr) to BLOCK-CYCLIC(r) redistribution (or vice versa), a processor can pack/unpack array elements into (from) messages directly. To evaluate the performance of our methods, we have implemented our methods along with Thakur's (1994) methods on an IBM SP2 parallel machine. The results show that the execution time of our algorithms is approximately 5% to 27% faster than that of Thakur's methods.

In this paper, we present message encoding techniques to improve the performance of BLOCK-CYCLIC(kr) to BLOCK-CYCLIC(r) (and vice versa) array redistribution algorithms. The message encoding techniques are machine independent and could be used with different algorithms. By incorporating the techniques in array redistribution algorithms, one can reduce the computation overheads and improve the overall performance of array redistribution algorithms. To evaluate the performance of the techniques, we have implemented the message encoding techniques into some array redistribution algorithms on an IBM SP2 parallel machine. The experimental results show that the execution time of array redistribution algorithms with the message encoding techniques is 3% to 22% faster than those without the message encoding techniques.

Abstract To efficiently execute a finite element program on a 2D torus, we need to map nodes of the corresponding finite element graph to processors of a 2D torus such that each processor has approximately the same amount of computational load and the communication among processors is minimized. If nodes of a finite element graph do not increase during the execution of a program, the mapping only needs to be performed once. However, if a finite element graph is solution‐adaptive, that is, nodes of a finite element graph increase discretely due to the refinement of some finite elements during the execution of a program, a dynamic load‐balancing algorithm has to be performed many times in order to balance the computational load of processors while keeping the communication cost as low as possible. In the paper we propose a parallel dynamic load‐balancing algorithm (LB) to deal with the load‐imbalancing problem of a solution‐adaptive finite element program on a 2D torus. The algorithm uses an iterative approach to achieve load‐balancing. We have implemented the proposed algorithm along with two parallel mapping algorithms, parallel orthogonal recursive bisection (ORB) and parallel recursive mincut bipartitioning (MC), on a simulated 2D torus. Three criteria, the execution time of load‐balancing algorithms, the computation time of an application program under different load balancing algorithms, and the total execution time of an application program (under several refinement phases) are used for performance evaluation. Simulation results show that (1) the execution of LB is faster than those of MC and ORB; (2) the mappings of LB are better than those of ORB and MC; and (3) the speedups of LB are better than those of ORB and MC.

To efficiently execute a finite element program on a hypercube, we need to map nodes of the corresponding finite element graph to processors of a hypercube such that each processor has approximately the same amount of computational load and the communication among processors is minimized. If the number of nodes of a finite element graph will not be increased during the execution of a program the mapping only needs to be performed once. However, if a finite element graph is solution-adaptive, that is, the number of nodes will be increased discretely due to the refinement of some finite elements during the execution of a program, a run-time load balancing algorithm has to be performed many times in order to balance the computational load of processors while keeping the communication cost as low as possible. In this paper, we propose a parallel iterative load balancing algorithm (ILB) to deal with the load imbalancing problem of a solution-adaptive finite element program. The proposed algorithm has three properties. First, the algorithm is simple and easy to implement. Second, the execution of the algorithm is fast. Third, it guarantees that the computational load will be balanced after the execution of the algorithm.

The authors discuss applications of BTDH (bottom-up top-down duplication heuristic) to list scheduling algorithms (LSAs). There are two ways to use BTDH for LSAs. BTDH can be used with an LSA to form a new scheduling algorithm (LSA/BTDH), and it can be used as a pure optimization algorithm for an LSA (LSA-BTDH). BTDH has been applied with two well-known LSAs: the highest level first with estimated time (HLFET) and the earlier task first (ETF) heuristics. Simulation results show that, given a directed acyclic growth (DAG), the graph parallelism of the DAG can accurately predict the number of processors to be used such that a good scheduling length and a good resource utilization (or efficiency) can be achieved simultaneously. In terms of speedups, LSA/BTDH >or= LSA-BTDH >or= ETF >or= HLFET. Experimental results of scheduling FFT programs, which are written in a single program multiple data (SPMD) programming approach, on NCUBE-2 are also presented. The results confirm the simulation results and show that the speedups of LSA/BTDH and LSA-BTDH are better than the speedups of LSAs.>