Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Institution
Articles 1 - 16 of 16
Full-Text Articles in Physical Sciences and Mathematics
Efficient Filters For Geometric Intersection Computations Using Gpu, Yiming Liu, Satish Puri
Efficient Filters For Geometric Intersection Computations Using Gpu, Yiming Liu, Satish Puri
Computer Science Faculty Research and Publications
Geometric intersection algorithms are fundamental in spatial analysis in Geographic Information System (GIS). Applying high performance computing to perform geometric intersection on huge amount of spatial data to get real-time results is necessary. Given two input geometries (polygon or polyline) of a candidate pair, we introduce a new two-step geospatial filter that first creates sketches of the geometries and uses it to detect workload and then refines the sketches by the common areas of sketches to decrease the overall computations in the refine phase. We call this filter PolySketch-based CMBR (PSCMBR) filter. We show the application of this filter in …
A Parallel Mesh Generator In 3d/4d, Kirill Voronin
A Parallel Mesh Generator In 3d/4d, Kirill Voronin
Portland Institute for Computational Science Publications
In the report a parallel mesh generator in 3d/4d is presented. The mesh generator was developed as a part of the research project on space-time discretizations for partial differential equations in the least-squares setting. The generator is capable of constructing meshes for space-time cylinders built on an arbitrary 3d space mesh in parallel. The parallel implementation was created in the form of an extension of the finite element software MFEM. The code is publicly available in the Github repository
A Speculative Approach To Parallelization In Particle Swarm Optimization, Matthew Gardner, Andrew Mcnabb, Kevin Seppi
A Speculative Approach To Parallelization In Particle Swarm Optimization, Matthew Gardner, Andrew Mcnabb, Kevin Seppi
Faculty Publications
Particle swarm optimization (PSO) has previously been parallelized primarily by distributing the computation corresponding to particles across multiple processors. In these approaches, the only benefit of additional processors is an increased swarm size. However, in many cases this is not efficient when scaled to very large swarm sizes (on very large clusters). Current methods cannot answer well the question: “How can 1000 processors be fully utilized when 50 or 100 particles is the most efficient swarm size?” In this paper we attempt to answer that question with a speculative approach to the parallelization of PSO that we refer to as …
Parallel Learning To Rank For Information Retrieval, Shuaiqiang Wang, Byron J. Gao, Ke Wang, Hady W. Lauw
Parallel Learning To Rank For Information Retrieval, Shuaiqiang Wang, Byron J. Gao, Ke Wang, Hady W. Lauw
Research Collection School Of Computing and Information Systems
Learning to rank represents a category of effective ranking methods for information retrieval. While the primary concern of existing research has been accuracy, learning efficiency is becoming an important issue due to the unprecedented availability of large-scale training data and the need for continuous update of ranking functions. In this paper, we investigate parallel learning to rank, targeting simultaneous improvement in accuracy and efficiency.
A Noise Reducing Sampling Approach For Uncovering Critical Properties In Large Scale Biological Networks, Karthik Duraisamy, Kathryn Dempsey Cooper, Hesham Ali, Sanjukta Bhowmick
A Noise Reducing Sampling Approach For Uncovering Critical Properties In Large Scale Biological Networks, Karthik Duraisamy, Kathryn Dempsey Cooper, Hesham Ali, Sanjukta Bhowmick
Interdisciplinary Informatics Faculty Proceedings & Presentations
A correlation network is a graph-based representation of relationships among genes or gene products, such as proteins. The advent of high-throughput bioinformatics has resulted in the generation of volumes of data that require sophisticated in silico models, such as the correlation network, for in-depth analysis. Each element in our network represents expression levels of multiple samples of one gene and an edge connecting two nodes reflects the correlation level between the two corresponding genes in the network according to the Pearson correlation coefficient. Biological networks made in this manner are generally found to adhere to a scale-free structural nature, that …
A Systolic Algorithm To Process Compressed Binary Images, Fikret Erçal, Mark Allen, Hao Feng
A Systolic Algorithm To Process Compressed Binary Images, Fikret Erçal, Mark Allen, Hao Feng
Computer Science Faculty Research & Creative Works
A new systolic algorithm which computes image differences in run-length encoded (RLE) format is described. The binary image difference operation is commonly used in many image processing applications including automated inspection systems, character recognition, fingerprint analysis, and motion detection. The efficiency of these operations can be improved significantly with the availability of a fast systolic system that computes the image difference as described in this paper It is shown that for images with a high similarity measure, the time complexity of the systolic algorithm is small and in some cases constant with respect to the image size. The time for …
An Efficient Parallel Algorithm For High Dimensional Similarity Join, Khaled Alsabti, Sanjay Ranka, Vineet Singh
An Efficient Parallel Algorithm For High Dimensional Similarity Join, Khaled Alsabti, Sanjay Ranka, Vineet Singh
Electrical Engineering and Computer Science - All Scholarship
Multidimensional similarity join finds pairs of multi-dimensional points that are within some small distance of each other: The 6-k-d-B tree has been proposed as a data structure that scales better as the number of dimensions in-creases compared to previous data structures. We present a cost model of the E-k-d-B tree and use it to optimize the leaf size. We present novel parallel algorithms for the similarity join using the E-k-d-B tree. A load-balancing strategy based on equi-depth histograms is shown to work well for uniform or low-skew situations, whereas another based on weighted equi-depth histograms works far better for high-skew …
A Fast Parallel Algorithm To Recognize P4-Sparse Graphs, Rong Lin, Stephan Olariu
A Fast Parallel Algorithm To Recognize P4-Sparse Graphs, Rong Lin, Stephan Olariu
Computer Science Faculty Publications
A number of problems in mobile computing, group-based collaboration, automated theorem proving, networking, scheduling, and cluster analysis suggested the study of graphs featuring certain “local density” characteristics. Typically, the notion of local density is equated with the absence of chordless paths of length three or more. Recently, a new metric for local density has been proposed, allowing a number of such induced paths to occur. More precisely, a graphG is called P4-sparse if no set of five vertices inG induces more than one chordless path of length three. P4-sparse graphs generalize the well-known class of cographs corresponding to …
Time-Optimal Tree Computations On Sparse Meshes, D. Bhagavathi, V. Bokka, H. Gurla, S. Olariu, J. L. Schwing
Time-Optimal Tree Computations On Sparse Meshes, D. Bhagavathi, V. Bokka, H. Gurla, S. Olariu, J. L. Schwing
Computer Science Faculty Publications
The main goal of this work is to fathom the suitability of the mesh with multiple broadcasting architecture (MMB) for some tree-related computations. We view our contribution at two levels: on the one hand, we exhibit time lower bounds for a number of tree-related problems on the MMB. On the other hand, we show that these lower bounds are tight by exhibiting time-optimal tree algorithms on the MMB. Specifically, we show that the task of encoding and/or decoding n-node binary and ordered trees cannot be solved faster than Ω(log n) time even if the MMB has an infinite …
Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih
Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih
Computer Science: Faculty Publications and Other Works
We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that are known to have linear- time sequential solutions rather than limiting attention to the "river-routing" context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN / lglgN) time on a (common) CRCW PRAM, both with optimal work (processor- time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor …
Time- And Cost-Optimal Parallel Algorithms For The Dominance And Visibility Graphs, D. Bhagavathi, H. Gurla, S. Olariu, J. L. Schwing, J. Zhang
Time- And Cost-Optimal Parallel Algorithms For The Dominance And Visibility Graphs, D. Bhagavathi, H. Gurla, S. Olariu, J. L. Schwing, J. Zhang
Computer Science Faculty Publications
The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non-overlapping rectangles in the plane. These graphs are intended to capture various visibility relations amongst the rectangles in the collection. The contribution of this paper is to propose time- and cost-optimal algorithms to construct two such graphs, namely, the dominance graph (DG, for short) and the visibility graph (VG, for short). Specifically, we show that with a collection of n non-overlapping rectangles as input, both these structures can be constructed in θ (log n) time using n processors in the CREW model.
Parallel Divide And Conquer, Per Brinch Hansen
Parallel Divide And Conquer, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
We develop a generic divide and conquer algorithm for a parallel tree machine. From the generic algorithm we derive balanced, parallel versions of quicksort and the fast Fourier transform by substitution of data types, variables and statements. The performance of these algorithms is analyzed and measured on a Computing Surface configured as a tree machine with distributed memory.
Do Hypercubes Sort Faster Than Tree Machines?, Per Brinch Hansen
Do Hypercubes Sort Faster Than Tree Machines?, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
We develop a balanced, parallel quicksort algorithm for a hypercube and compare it with a similar algorithm for a binary tree machine. The performance of the hypercube algorithm is measured on a Computing Surface.
A Generic Multiplication Pipeline, Per Brinch Hansen
A Generic Multiplication Pipeline, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This paper illustrates the benefits of developing generic algorithms for parallel programming paradigms which can be adapted to different applications. We consider a combinatorial problem called tuple multiplication. This paradigm includes matrix multiplication and the all-pairs shortest paths problem as special cases. We develop a generic pipeline for tuple multiplication. From the generic algorithm we derive pipelines for matrix multiplication and shortest paths computation by making substitutions of data types and functions. The performance of the matrix multiplication pipeline is analyzed and measured on a Computing Surface.
A Simulation Of Demand-Driven Dataflow: Translation From Lucid Into Mdc Language, George K. Thiruvathukal, Thomas W. Christopher
A Simulation Of Demand-Driven Dataflow: Translation From Lucid Into Mdc Language, George K. Thiruvathukal, Thomas W. Christopher
Computer Science: Faculty Publications and Other Works
Message Driven Computation (MDC) is a model of computation with which they have been experimenting at the Illinois Institute of Technology. The authors aim to prove the viability of MDC in practice for the expression of parallel algorithms and the implementation of functional and dataflow programming languages. In the paper they discuss their implementation of the Lucid programming language in MDC. The discussion presents a subset of Lucid which illustrates the principles of Lucid, Message Driven Computing, and the translation into and the interpretation of dataflow graphs.
The Nature Of Parallel Programming, Per Brinch Hansen
The Nature Of Parallel Programming, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
Parallel programming is the art of writing programs for computers that perform many operations simultaneously. This essay discusses the nature of parallel programming without going into technical details. It uses a sorting problem to illustrate what it means to solve a problem in parallel, how we write parallel programs, how parallel computers execute them, and how fast they run. The author expects that scientific users of parallel computers may find ease of programming more important than maximum performance. He suggests ways to make this possible.