Computing Privacy-Preserving Edit Distance and Smith-Waterman Problems on the GPU Architecture

Shi Pu, Jyh-Charn Liu
Department of Computer Science and Engineering, Texas A&M University, College Station, TX 77840
Cryptology ePrint Archive: Report 2013/204, 2013

   author={Shi Pu, Jyh-Charn Liu},

   title={Computing Privacy-Preserving Edit Distance and Smith-Waterman Problems on the GPU Architecture},

   howpublished={Cryptology ePrint Archive, Report 2013/204},




Download Download (PDF)   View View   Source Source   



This paper presents privacy-preserving, parallel computing algorithms on a graphic processing unit (GPU) architecture to solve the Edit-Distance (ED) and the Smith-Waterman (SW) problems. The ED and SW problems are formulated into dynamic programming (DP) computing problems, which are solved using the Secure Function Evaluation (SFE) to meet privacy protection requirements, based on the semi-honest security model. Major parallelization techniques include mapping of variables to support collision-free parallel memory access, scheduling and mapping of gate garblers on GPU devices to maximize GPU device utilization, and latency minimization of context switch for computing steps in the DP matrix. A pipelined GPU-CPU interface is developed to mask latency of CPU housekeeping components. The new solutions were tested on a Xeon E5504 at 2GHz plus a GTX-680 GPU (as generator), connecting an i7-3770K at 3.5GHz plus a GTX-680 GPU (as evaluator) via local Internet. A 5000×5000 8-bit alphabet ED problem requires roughly 1.88 billion non-free gates, and the running time of around 26 minutes (roughly 1.209×10^6 gate/second). A 60×60 SW problem is computed in around 16.79 seconds. Compared to the state of art performance [5], we achieved the acceleration factor of 12.5x for the ED problem, and 24.7x for the SW problem.
VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

* * *

* * *

Follow us on Twitter

HGPU group

1496 peoples are following HGPU @twitter

Like us on Facebook

HGPU group

252 people like HGPU on Facebook

* * *

Free GPU computing nodes at hgpu.org

Registered users can now run their OpenCL application at hgpu.org. We provide 1 minute of computer time per each run on two nodes with two AMD and one nVidia graphics processing units, correspondingly. There are no restrictions on the number of starts.

The platforms are

Node 1
  • GPU device 0: nVidia GeForce GTX 560 Ti 2GB, 822MHz
  • GPU device 1: AMD/ATI Radeon HD 6970 2GB, 880MHz
  • CPU: AMD Phenom II X6 @ 2.8GHz 1055T
  • RAM: 12GB
  • OS: OpenSUSE 13.1
  • SDK: nVidia CUDA Toolkit 6.5.14, AMD APP SDK 3.0
Node 2
  • GPU device 0: AMD/ATI Radeon HD 7970 3GB, 1000MHz
  • GPU device 1: AMD/ATI Radeon HD 5870 2GB, 850MHz
  • CPU: Intel Core i7-2600 @ 3.4GHz
  • RAM: 16GB
  • OS: OpenSUSE 12.3
  • SDK: AMD APP SDK 3.0

Completed OpenCL project should be uploaded via User dashboard (see instructions and example there), compilation and execution terminal output logs will be provided to the user.

The information send to hgpu.org will be treated according to our Privacy Policy

HGPU group © 2010-2015 hgpu.org

All rights belong to the respective authors

Contact us: