Search

Voting algorithms, such as histogram and Hough transforms, are frequently used algorithms in various domains, such as statistics and image processing. Algorithms in these domains may be accelerated using GPUs. Implementing voting algorithms efficiently on a GPU however is far from trivial due to irregularities and unpredictable memory accesses. Existing GPU implementations therefore target only specific voting algorithms while we propose in this work a methodology which targets voting algorithms in general. This methodology is used in gpu-vote, a framework to accelerate current and future voting algorithms on a GPU without significant programming effort. We classify voting algorithms into four categories. We describe a transformation to merge categories which enables gpu-vote to have a single implementation for all voting algorithms. Despite the generality of gpu-vote, being able to handle various voting algorithms, its performance is not compromised. Compared to recently published GPU implementations of the Hough transform and the histogram algorithms, gpu-vote yields a 11% and 38% lower execution time respectively. Additionally, we give an accurate and intuitive performance prediction model for the generalized GPU voting algorithm. Our model can predict the execution time of gpu-vote within an average absolute error of 5%.

Let \({\mathcal{F}}\) be a family of subsets of the ground set [n] = {1, 2, . . . , n}. For each \({i \in [n]}\) we let \({p(\mathcal{F},i)}\) be the number of pairs of subsets that differ in the element i and exactly one of them is in \({\mathcal{F}}\). We interpret \({p(\mathcal{F},i)}\) as the influence of that element. The normalized Banzhaf vector of \({\mathcal{F}}\), denoted \({B(\mathcal{F})}\), is the vector \({(B(\mathcal{F},1),\dots,B(\mathcal{F},n))}\), where \({B(\mathcal{F},i)=\frac{p(\mathcal{F},i)}{p(\mathcal{F})}}\) and \({p(\mathcal{F})}\) is the sum of all \({p(\mathcal{F},i)}\). The Banzhaf vector has been studied in the context of measuring voting power in voting games as well as in Boolean circuit theory. In this paper we investigate which non-negative vectors of sum 1 can be closely approximated by Banzhaf vectors of simple voting games. In particular, we show that if a vector has most of its weight concentrated in k < n coordinates, then it must be essentially the Banzhaf vector of some simple voting game with n − k dummy voters.

There are many situations wherein a group of individuals (e.g., voters, experts, sports writers) must produce an ordered list of ‘best’ alternatives selected from a given group of alternatives (e.g., candidates, proposals, sports teams). Two long established mechanisms that have been used for this task are ‘Zermelo’s Ranking Method’ (1929) and ‘Borda’s Voting Scheme’ (1781). The main purpose of this paper is to point out that they are, under certain common circumstances, identical. We then show that Zermelo’s Method can be used in situations that Borda’s Method is not designed to handle.

Background Genes work in concert as a system, not as independent entities, to mediate disease states. There has been considerable interest in understanding variations in molecular signatures between normal and disease states. The selective-voting convex-hull ensemble procedure accommodates molecular heterogeneity within and between groups and allows retrieval of sample-specific sets and investigation of variations in individual networks relevant to personalized medicine[1]. The work here describes using the convex-hull voting method on a large data set. Using parallelization techniques, we predict that we can execute the convex-hull voting algorithm on the University of Kentucky cluster (DLX) using a dataset much too large to run in a feasible time on a single machine.