Jin / Rana / Pan Algorithms and Architectures for Parallel Processing

7th International Conference, ICA3PP 2007, Hangzhou, China, June 11-14, 2007, Proceedings
2007
ISBN: 978-3-540-72905-1
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 4494, 523 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Parallel and distributed computing in the 1980s and 1990s had great in?uence onapplication developmentin science, engineering andbusiness computing. The improvements in computation and communication capabilities have enabled the creation of demanding applications in critical domains such as the environment, health, aerospace, and other areas of science and technology. Similarly, new classesofapplicationsareenabledbytheavailabilityofheterogeneouslarge-scale distributed systems which are becoming available nowadays (based on techno- giessuchasgridandpeer-to-peersystems).Parallelcomputingsystemsexploita large diversity of computer architectures, from supercomputers, shared-memory or distributed-memory multi processors, to local networks and clusters of p- sonal computers. With the recent emergence of multi core architectures, parallel computing is now set to achieve “mainstream” status. Approaches that have been advocated by parallelcomputing researchersin the past are now being utilized in a number of software libraries and hardware systems that are available for everyday use. Parallel computing ideas have also come to dominate areas such as multi user gaming (especially in the development of gaming engines based on “cell” arc- tectures) – often ignored by many “serious” researchers in the past, but which now are set to have a growing user base of tens of millions across the world. In recent years, focus has also shifted to support energy e?ciency in com- tation, with some researchers proposing a new metric of performance based on Flops/Watt.

Zielgruppe

Research

Autoren/Hrsg.

Jin, Haj

Jin, Hai

Rana, Omer F.

Pan, Yi

Prasanna, Victor K.

Inhaltsverzeichnis

Keynote Speech.- RSM-Based Gossip on P2P Network.- Invited Papers.- AnyServer: Ubiquitous Real-Time Multimedia Communication System.- Performance Analysis of Interconnection Networks Under Bursty and Batch Arrival Traffic.- Protocols for Traffic Safety Using Wireless Sensor Network.- Track 1: Parallel Algorithms.- A Lazy EDF Interrupt Scheduling Algorithm for Multiprocessor in Parallel Computing Environment.- Efficient Representations of Row-Sorted 1-Variant Matrices for Parallel String Applications.- PHC: A Rapid Parallel Hierarchical Cubing Algorithm on High Dimensional OLAP.- A Time and Interaction Model for Open Distributed Timing Computation.- Efficient Linkable Ring Signatures and Threshold Signatures from Linear Feedback Shift Register.- An Implementation of Parallel Eigenvalue Computation Using Dual-Level Hybrid Parallelism.- An Improved Algorithm for Alhusaini’s Algorithm in Heterogeneous Distributed Systems.- Track 2: Parallel Architecture.- Fuzzy-Grey Prediction Based Dynamic Failure Detector for Distributed Systems.- A Two-Level Directory Organization Solution for CC-NUMA Systems.- A Framework of Software Component Adaptation.- A Parallel Infrastructure on Dynamic EPIC SMT.- The Thread Migration Mechanism of DSM-PEPE.- EH*RS: A High-Availability Scalable Distributed Data Structure.- Optimizing Stream Organization to Improve the Performance of Scientific Computing Applications on the Stream Processor.- A Parallel Architecture for Motion Estimation and DCT Computation in MPEG-2 Encoder.- EOP: An Efficient Object Placement and Location Algorithm for OBS Cluster.- Track 3: Grid Computing.- Data Interoperation Between ChinaGrid and SRB.- Redundant Parallel File Transfer with Anticipative Recursively-Adjusting Scheme in Data Grids.- A Strategy-ProofCombinatorial Auction-Based Grid Resource Allocation System.- Method for Computational Grids Resources Allocate Based on Auction and Utility Analyses.- Service Dependency Model for Dynamic and Stateful Grid Services.- Automatic Conceptual Indexing of Web Services and Its Application to Service Retrieval.- Design and Implementation of Computational Bioinformatics Grid Services on GT4 Platforms.- On-Demand Capacity Framework.- Track 4: Peer-to-Peer Technologies.- An Interest-Based Intelligent Link Selection Algorithm in Unstructured P2P Environment.- Keyword Search in DHT-Based Peer-to-Peer Networks.- Implementing Digital Right Management in P2P Content Sharing System.- IPBGA: A Hybrid P2P Based Grid Architecture by Using Information Pool Protocol.- Understanding Peer Behavior and Designing Incentive Mechanism in Peer-to-Peer Networks: An Analytical Model Based on Game Theory.- An Efficient Source Peer Selection Algorithm in Hybrid P2P File Sharing Systems.- A New k-Graph Partition Algorithm for Distributed P2P Simulation Systems.- Track 5: Advanced Network Technologies.- A Dominant Input Stream for LUD Incremental Computing on a Contention Network.- A Double-Objective Genetic Algorithm for Parity Declustering Optimization in Networked RAID.- Hybrid Diffusion Schemes for Load Balancing on OTIS-Networks.- A Dynamic Localized Minimum-Energy Agent Tree-Based Data Dissemination Scheme for Wireless Sensor Networks.- THIN: A New Hierarchical Interconnection Network-on-Chip for SOC.- Architecture of Adaptive Spam Filtering Based on Machine Learning Algorithms.- On the Power-Law of the Internet and the Hierarchy of BGP Convergence.- GDED-X Schemes for Load Balancing on Heterogeneous OTIS-Networks.- Added.- A Generalized Critical Task Anticipation Technique for DAG Scheduling.

Leseproben

PHC: A Rapid Parallel Hierarchical Cubing Algorithm on High Dimensional OLAP. (p. 72-73)

Kongfa Hu1, Ling Chen1, and Yixin Chen2
1 Department of Computer Science and Engineering, Yangzhou University, 225009, China
2 Department of Computer Science and Engineering, Washington University, 63130, USA

Abstract. Data cube has been playing an essential role in OLAP (online analytical processing). The pre-computation of data cubes is critical for improving the response time of OLAP systems. However, as the size of data cube grows, the time it takes to perform this pre-computation becomes a significant performance bottleneck. In a high dimensional OLAP, it might not be practical to build all these cuboids and their indices. In this paper, we propose a parallel hierarchical cubing algorithm, based on an extension of the previous minimal cubing approach. The algorithm has two components: decomposition of the cube space based on multiple dimension attributes, and an efficient OLAP query engine based on a prefix bitmap encoding of the indices. This method partitions the high dimensional data cube into low dimensional cube segments. Such an approach permits a significant reduction of CPU and I/O overhead for many queries by restricting the number of cube segments to be processed for both the fact table and bitmap indices. The proposed data allocation and processing model support parallel I/O and parallel processing, as well as load balancing for disks and processors. Experimental results show that the proposed parallel hierarchical cubing method is significantly more efficient than other existing cubing methods. Keywords: data cube, parallel hierarchical cubing algorithm (PHC), high dimensional OLAP.

1 Introduction

Data warehouses integrate massive amounts of data from multiple sources and are primarily used for decision support purposes. They have to process complex analytical queries for different access forms such as OLAP (on-line analytical processing), data mining, etc. OLAP refers to the technologies that allow users to efficiently retrieve data from the data warehouse for decision support purposes [1]. A lot of research has been done in order to improve the OLAP query performance and to provide fast response times for queries on large data warehouses. Efficient indexing [2], materialization [3] and data cubing [4] are common techniques to speed up the OLAP query processing. Many efficient cube computation algorithms have been proposed recently, such as BUC [5], H-cubing [6], Quotient cubing [7], and Starcubing [8]. However, in the large data warehouse applications, such as bioinformatics, the data usually has high dimensionality with more than 100 dimensions. Since data cube grows exponentially with the number of dimensions, it is generally too costly in both computation time and storage space to materialize a full high-dimensional data cube. For example, a data cube of 100 dimensions, each with 100 distinct values, may contain as many as 101100 cells. If we consider the dimension hierarchies, the aggregate cell will increase even more tremendously. Although condensed cube [9], dwarf cube [10], or star cubes [8] can delay the explosion, it does not solve the fundamental problem [11]. The minimal cubing approach from Li and Han [11] can alleviate this problem, but does not consider the dimension hierarchies and cannot efficiently handle OLAP queries. In this paper, we develop a feasible parallel hierarchical cubing algorithm (PHC) that supports dimension hierarchies for highdimensional data cubes and answers OLAP queries efficiently. The algorithm decomposes a multi-dimensional hierarchical data cube into smaller cube segments. This proposed data allocation and processing model supports parallel I/O and parallel processing as well as load balancing for disks and processors. This proposed cubing algorithm is an efficient and scalable parallel processing algorithm for cube computation.