In order to facilitate efficient query processing, the information contained in data warehouses is typically stored as a set of materialized views. Deciding which views to materialize represent a challenge in order to...
详细信息
ISBN:
(纸本)9783540695004
In order to facilitate efficient query processing, the information contained in data warehouses is typically stored as a set of materialized views. Deciding which views to materialize represent a challenge in order to minimize view maintenance and query processing costs. Some existing approaches are applicable only for small problems, which are far from reality. In this paper we introduce a new approach for materialized view selection using parallel Simulated Annealing (PSA) that selects views from an input Multiple View processing Plan (MVPP). With PSA, we are able to perform view selection on MVPPs having hundreds of queries and thousands of views. Also, in our experimental study we show that our method provides a significant improvement in the quality of the obtained set of materialized views over existing heuristic and sequential simulated annealing algorithms.
parallel computers provide an efficient and economical way to solve large-scale and/or time-constrained scientific, engineering, and industry problems. Consequently, there is a need to predict the performance order of...
详细信息
ISBN:
(纸本)9783540695004
parallel computers provide an efficient and economical way to solve large-scale and/or time-constrained scientific, engineering, and industry problems. Consequently, there is a need to predict the performance order of both deterministic and non-deterministic parallelalgorithms. the performance prediction of the traveling salesman problem (TSP) is a challenging problem because similar input data sets may cause significant variability in execution times. parallel performance of data-dependent algorithms depends on the problem size, the number of processors, and other parameters. Discovering the main other parameters is the real key to obtain a good estimation of performance order. this paper presents a novel methodology to the problem of predicting the performance of a parallel algorithm for solving the TSP. the entire process explores data in search of patterns and/or relationships detecting the main parameters that affect performance. then, it uses the measured values for this limited number of inputs to produce a multiple-linear-regression model. Finally, the regression equation allows for predicting how the algorithm will respond when given new input data sets. the preliminary experimental results are quite promising.
In this paper we present a novel and complete approach on how to encapsulate parallelism for relational database query execution that strives for maximum resource utilization for both CPU and disk activities. Its simp...
详细信息
ISBN:
(纸本)9783540695004
In this paper we present a novel and complete approach on how to encapsulate parallelism for relational database query execution that strives for maximum resource utilization for both CPU and disk activities. Its simple and robust design is capable of modeling intra- and inter-operator parallelism for one or more parallel queries in a most natural way. In addition, encapsulation guarantees that the bulk of relational operators can remain unmodified, as long as their implementation is thread-safe. We will show, that withthis approach, the problem of scheduling parallel tasks is generalized, so that it can be safely entrusted to the underlying operating system (OS) without suffering any performance penalties. On the contrary, relocation of all scheduling decisions from the DBMS to the OS guarantees a centralized and therefore near-optimal resource allocation (depending on the OS's abilities) for the complete system that is hosting the database server as one of its tasks. Moreover, withthis proposal, query parallelization is fully transparent on the SQL interface of the database system. Configuration of the system for effective parallel query execution can be adjusted by the DB administrator by setting two descriptive tuning parameters. A prototype implementation has been integrated into the Transbase (R) relational DBMS engine.
An analysis of a parallel solution of N-2-1 Puzzle using clusters, is presented. this problem is interesting due to its complexity and related applications, particularly in the field of robotics. A variation of classi...
详细信息
ISBN:
(纸本)9789537138127
An analysis of a parallel solution of N-2-1 Puzzle using clusters, is presented. this problem is interesting due to its complexity and related applications, particularly in the field of robotics. A variation of classic heuristics for forecasting the work to be done in order to reach a solution is analyzed, and it is shown that its use significantly improves the time of sequential algorithm A*. then, a parallel solution on a distributed architecture is presented and speedup is analyzed based on the number of processors, efficiency, and the possible superlinearity when scaling the problem.
Real time reconfigurability of the digital backend of UWB receiver has a potential to achieve significant power saving during the acquisition and synchronisation mode of receiver operation. this paper proposes a novel...
详细信息
ISBN:
(纸本)9781424422166
Real time reconfigurability of the digital backend of UWB receiver has a potential to achieve significant power saving during the acquisition and synchronisation mode of receiver operation. this paper proposes a novel real time reconfigurabilily algorithm which can estimate number of parallel blocks required for the receiver operation for a particular channel condition and switches off the unwanted blacks. As a part of the real time reconfigurability algorithm, modified CLEAN and priority encoder algorithms are proposed for estimation and effective translation algorithms are developed in order to achieve significant reduction in receiver backend power consumption.
Traditionally, the block-based medial axis transform (BB-MAT) and the chessboard distance transform (CDT) were usually viewed as two completely different image computation problems, especially for three dimensional (3...
详细信息
ISBN:
(纸本)9783540695004
Traditionally, the block-based medial axis transform (BB-MAT) and the chessboard distance transform (CDT) were usually viewed as two completely different image computation problems, especially for three dimensional (3D) space. We achieve the computation of the 3D CDT problem by implementing the 3D BB-MAT algorithm first. For a 3D binary image of size N-3, our parallel algorithm can be run in O(logN) time using N-3 processors on the concurrent read exclusive write (CREW) parallel random access machine (PRAM) model to solve both 3D BB-MAT and 3D CDT problems, respectively. In addition, we have implemented a message passing interface (MPI) program on an AMD Opteron Model 270 cluster system to verify the proposed parallel algorithm, since the PRAM model is not available in the real world. the experimental results show that the speedup is saturated when the number of processors used is more than four, regardless of the problem size.
the knapsack problem is a typical one of NPC problems, which is easy to be described but difficult to be solved. It is very important in theory and practice to study it. Nowadays there is a variety of research in algo...
详细信息
ISBN:
(纸本)9780769533827
the knapsack problem is a typical one of NPC problems, which is easy to be described but difficult to be solved. It is very important in theory and practice to study it. Nowadays there is a variety of research in algorithm for solving it. As the parallelprocessing technologies develop, the research of effective parallelalgorithms for this problem attracts much attention. To run those algorithms needs high level hardware and high performance parallel computers. Using mobile agent technologies, a more effective model to solve the complex distributed problems can be established. Combines mobile agent withthe traditional parallel algorithm, the process in a parallel computer can be evolved into the one performed by some ordinary computers. this can avoid the limitation of experiment conditions and provides convenience in practice. In this paper, a distributed algorithm is proposed for the 0-1 knapsack problem based on the mobile agent, and it is feasible and effective in theoretical analysis.
As current reasoning techniques are not designed for massive parallelisation, usage of parallel computation techniques in reasoning establishes a major research problem. I will propose two possibilities of applying pa...
详细信息
ISBN:
(纸本)9783540885634
As current reasoning techniques are not designed for massive parallelisation, usage of parallel computation techniques in reasoning establishes a major research problem. I will propose two possibilities of applying parallel computation techniques to ontology reasoning: parallelprocessing of independent ontological modules, and tailoring the reasoning algorithms to parallelarchitectures.
this paper examines the scalable parallel implementation of the QR factorization of a general matrix, targeting SMP and multi-core architectures. Two implementations of algorithms-by-blocks are presented. Each impleme...
详细信息
ISBN:
(纸本)9780769530895
this paper examines the scalable parallel implementation of the QR factorization of a general matrix, targeting SMP and multi-core architectures. Two implementations of algorithms-by-blocks are presented. Each implementation views a block of a matrix as the fundamental unit of data, and likewise, operations over these blocks as the primary unit of computation. the first is a conventional blocked algorithm similar to those included in libFLAME and LAPACK but expressed in a way that allows operations in the so-called critical path of execution to be computed as soon as their dependencies are satisfied. the second algorithm captures a higher degree of parallelism with an approach based on Givens rotations while preserving the performance benefits of algorithms based on blocked Householder transformations. We show that the implementation effort is greatly simplified by expressing the algorithms in code withthe FLAME/FLASH API, which allows matrices stared by blocks to be viewed and managed as matrices of matrix blocks. the SuperMatrix run-time system utilizes FLASH to assemble and represent matrices but also provides out-of-order scheduling of operations that is transparent to the programmer Scalability of the solution is demonstrated on ccNUMA platform with 16 processors and an SMP architecture with 16 cores.
this paper presents a hardware implementation of a secure and reliable k-out-of-n threshold based secret image sharing method. the secret image is divided into n image shares so that any k image shares are sufficient ...
详细信息
ISBN:
(纸本)9780769534343
this paper presents a hardware implementation of a secure and reliable k-out-of-n threshold based secret image sharing method. the secret image is divided into n image shares so that any k image shares are sufficient to reconstruct the secret image in a lossless manner, but (k-1) or fewer image shares cannot reveal anything about the secret image. this secret sharing method comprises multiple independent computations which are conducive to parallelprocessingarchitectures. Fine-grained field programmable gate array (FPGA) architectures are the near optimal hardware platform for performing parallelprocessing. this paper illustrates the design and implementation of the secret image sharing method for 8-bit grayscale images on an FPGA which enhances execution time. On average, it was found that the FPGA. executes image sharing and reconstruction approximately 300 times faster than a microprocessor operating on the same image.
暂无评论