research-article

Public Access

Data Oblivious Algorithms for Multicores

Authors:

Vijaya Ramachandran,

Elaine ShiAuthors Info & Claims

SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures

Pages 373 - 384

https://doi.org/10.1145/3409964.3461783

Published: 06 July 2021 Publication History

Abstract

A data-oblivious algorithm is an algorithm whose memory access pattern is independent of the input values. We initiate the study of parallel data oblivious algorithms on realistic multicores, best captured by the binary fork-join model of computation. We present a data-oblivious CREW binary fork-join sorting algorithm with optimal total work and optimal (cache-oblivious) cache complexity, and in O(łog n łog łog n) span (i.e., parallel time); these bounds match the best-known bounds for binary fork-join cache-efficient insecure algorithms. Using our sorting algorithm as a core primitive, we show how to data-obliviously simulate general PRAM algorithms in the binary fork-join model with non-trivial efficiency, and we present data-oblivious algorithms for several applications including list ranking, Euler tour, tree contraction, connected components, and minimum spanning forest. All of our data oblivious algorithms have bounds that either match or improve over the best known bounds for insecure algorithms.

Complementing these asymptotically efficient results, we present a practical variant of our sorting algorithm that is self-contained and potentially implementable. It has optimal caching cost, and it is only a łog łog n factor off from optimal work and about a łog n factor off in terms of span. %moreover, it achieves small constant factors in its bounds. We also present an EREW variant with optimal work and caching cost, and with the same asymptotic span.

References

[1]

Umut A. Acar, Guy E. Blelloch, and Robert D. Blumofe. 2000. The Data Locality of Work Stealing. In Proceedings of the Twelfth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) (Bar Harbor, Maine, USA). Association for Computing Machinery, 1--12.

[2]

M. Ajtai, J. Komlós, and E. Szemerédi. 1983. An O(N Log N) Sorting Network. In STOC .

[3]

Nimar S. Arora, Robert D. Blumofe, and C. Greg Plaxton. 1998. Thread Scheduling for Multiprogrammed Multiprocessors. In Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) (Puerto Vallarta, Mexico). Association for Computing Machinery, New York, NY, USA, 119--129.

[4]

Gilad Asharov, T.-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. 2020 a. Bucket Oblivious Sort: An Extremely Simple Oblivious Sort. In 3rd Symposium on Simplicity in Algorithms, SOSA@SODA, Martin Farach-Colton and Inge Li Gørtz (Eds.). SIAM, 8--14.

[5]

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. 2020 b. Oblivious Parallel Tight Compaction. In Information-Theoretic Cryptography (ITC) .

[6]

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. 2020 c. Optimal Oblivious Parallel RAM . Manuscript in preparation. Personal communication with Asharov et al.

[7]

Marina Blanton, Aaron Steele, and Mehrdad Alisagari. 2013. Data-oblivious Graph Algorithms for Secure Computation and Outsourcing. In ASIA CCS .

[8]

Guy E. Blelloch, Rezaul A. Chowdhury, Phillip B. Gibbons, Vijaya Ramachandran, Shimin Chen, and Michael Kozuch. 2008. Provably Good Multicore Cache Performance for Divide-and-Conquer Algorithms. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (San Francisco, California). Society for Industrial and Applied Mathematics, USA, 501--510.

Digital Library

[9]

Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, and Harsha Vardhan Simhadri. 2011. Scheduling Irregular Parallel Computations on Hierarchical Caches. In Proceedings of the Twenty-Third Annual ACM Symposium on Parallelism in Algorithms and Architectures (San Jose, California, USA) (SPAA '11). Association for Computing Machinery, New York, NY, USA, 355--366. https://doi.org/10.1145/1989493.1989553

Digital Library

[10]

Guy E. Blelloch and Phillip B. Gibbons. 2004. Effectively Sharing a Cache among Threads. In Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (Barcelona, Spain). Association for Computing Machinery, New York, NY, USA, 235--244. https://doi.org/10.1145/1007912.1007948

[11]

Guy E. Blelloch, Phillip B. Gibbons, and Yossi Matias. 1999. Provably Efficient Scheduling for Languages with Fine-Grained Parallelism. J. ACM, Vol. 46, 2 (March 1999), 281--321. https://doi.org/10.1145/301970.301974

Digital Library

[12]

Guy E. Blelloch, Phillip B. Gibbons, and Harsha Vardhan Simhadri. 2010. Low Depth Cache-Oblivious Algorithms. In Proceedings of the Twenty-Second Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (Thira, Santorini, Greece). Association for Computing Machinery, New York, NY, USA, 189--199.

Digital Library

[13]

Robert D. Blumofe and Charles E. Leiserson. 1993. Space-Efficient Scheduling of Multithreaded Computations. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC) (San Diego, California, USA). Association for Computing Machinery, New York, NY, USA, 362--371.

[14]

Robert D. Blumofe and Charles E. Leiserson. 1999. Scheduling Multithreaded Computations by Work Stealing. J. ACM, Vol. 46, 5 (Sept. 1999), 720--748.

Digital Library

[15]

Elette Boyle, Kai-Min Chung, and Rafael Pass. 2015. Oblivious Parallel RAM. In Theory of Cryptography Conference (TCC) .

[16]

Zoran Budimlić, Vincent Cavé, Raghavan Raman, Jun Shirako, Saugnak Tacsundefinedrlar, Jisheng Zhao, and Vivek Sarkar. 2011. The Design and Implementation of the Habanero-Java Parallel Programming Language. In Proceedings of the ACM International Conference Companion on Object Oriented Programming Systems Languages and Applications Companion (OOPSLA) (Portland, Oregon, USA). Association for Computing Machinery, New York, NY, USA, 185--186. https://doi.org/10.1145/2048147.2048198

Digital Library

[17]

T.-H. Hubert Chan and Elaine Shi. 2017. Circuit OPRAM: Unifying Statistically and Computationally Secure ORAMs and OPRAMs. In Theory of Cryptography Conference, (TCC) .

[18]

T.-H. Hubert Chan, Kai-Min Chung, and Elaine Shi. 2017. On the Depth of Oblivious Parallel RAM. In Advances in Cryptology -- ASIACRYPT 2017 . Springer International Publishing, 567--597.

[19]

T-H. Hubert Chan, Yue Guo, Wei-Kai Lin, and Elaine Shi. 2018. Cache-Oblivious and Data-Oblivious Sorting and Applications. In SODA .

[20]

Philippe Charles, Christian Grothoff, Vijay Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph von Praun, and Vivek Sarkar. 2005. X10: An Object-Oriented Approach to Non-Uniform Cluster Computing. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA) (San Diego, CA, USA). Association for Computing Machinery, New York, NY, USA, 519--538.

Digital Library

[21]

Yi-Jen Chiang, Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, and Jeffrey Scott Vitter. 1995. External-Memory Graph Algorithms. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, USA) (SODA '95). Society for Industrial and Applied Mathematics, USA, 139--149.

Digital Library

[22]

Rezaul A. Chowdhury and Vijaya Ramachandran. 2008. Cache-efficient dynamic programming algorithms for multicores. In Proc. ACM SPAA.

[23]

Rezaul A. Chowdhury and Vijaya Ramachandran. 2010. The Cache-oblivious Gaussian Elimination Paradigm: Theoretical Framework, Parallelization and Experimental Evaluation. Theory of Computing Systems, Vol. 47, 1 (2010), 878--919. Preliminary version in SPAA 2007.

Digital Library

[24]

Rezaul Alam Chowdhury, Vijaya Ramachandran, Francesco Silvestri, and Brandon Blakeley. 2013. Oblivious algorithms for multicores and networks of processors. J. Parallel Distributed Comput., Vol. 73, 7 (2013), 911--925.

[25]

Richard Cole and Vijaya Ramachandran. 2010. Resource Oblivious Sorting on Multicores. In Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6--10, 2010, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 6198), Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis (Eds.). Springer, 226--237.

[26]

Richard Cole and Vijaya Ramachandran. 2012a. Efficient Resource Oblivious Algorithms for Multicores with False Sharing. In 26th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2012, Shanghai, China, May 21--25, 2012. IEEE Computer Society, 201--214.

[27]

Richard Cole and Vijaya Ramachandran. 2012b. Revisiting the cache miss analysis of multithreaded algorithms. In Proc. LATIN.

Digital Library

[28]

Richard Cole and Vijaya Ramachandran. 2013. Analysis of randomized work-stealing with false sharing. In Proc. IPDPS .

Digital Library

[29]

Richard Cole and Vijaya Ramachandran. 2017a. Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers. In Proc. ACM SPAA .

Digital Library

[30]

Richard Cole and Vijaya Ramachandran. 2017b. Resource Oblivious Sorting on Multicores. ACM Trans. Parallel Comput., Vol. 3, 4, Article 23 (March 2017), bibinfonumpages31 pages. Preliminary version in ICALP 2010.

Digital Library

[31]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition 3rd ed.). The MIT Press.

[32]

Matteo Frigo, Charles E Leiserson, Harald Prokop, and Sridhar Ramachandran. 1999. Cache-oblivious algorithms. In Foundations of Computer Science, 1999. 40th Annual Symposium on. IEEE, 285--297.

[33]

Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. 1998. The Implementation of the Cilk-5 Multithreaded Language. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation (PLDI) (Montreal, Quebec, Canada). Association for Computing Machinery, New York, NY, USA, 212--223. https://doi.org/10.1145/277650.277725

[34]

M. Frigo and V. Strumpen. 2009. The cache complexity of multithreaded cache-oblivious algorithms. Theory of Computing Systems, Vol. 45 (2009), 203--233.

Digital Library

[35]

Github. [n.d.]. https://github.com/oneapi-src/oneTBB .

[36]

O. Goldreich. 1987. Towards a theory of software protection and simulation by oblivious RAMs. In STOC .

[37]

Oded Goldreich and Rafail Ostrovsky. 1996. Software protection and simulation on oblivious RAMs. J. ACM (1996).

[38]

Michael T. Goodrich. 2014. Zig-zag Sort: A Simple Deterministic Data-oblivious Sorting Algorithm Running in O(N Log N) Time. In STOC .

Digital Library

[39]

Michael T. Goodrich, Olga Ohrimenko, and Roberto Tamassia. 2013. Graph Drawing in the Cloud: Privately Visualizing Relational Data Using Small Working Storage. In Graph Drawing, Walter Didimo and Maurizio Patrignani (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 43--54.

[40]

Michael T. Goodrich and Joseph A. Simons. 2014. Data-Oblivious Graph Algorithms in Outsourced External Memory. In Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19--21, 2014, Proceedings (Lecture Notes in Computer Science, Vol. 8881). Springer, 241--257.

[41]

Mohammad Islam, Mehmet Kuzu, and Murat Kantarcioglu. 2012. Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation. In Network and Distributed System Security Symposium (NDSS) .

[42]

Zahra Jafargholi, Kasper Green Larsen, and Mark Simkin. 2020. Optimal Oblivious Priority Queues and Offline Oblivious RAM. In ACM-SIAM SODA .

[43]

Richard M. Karp and Vijaya Ramachandran. 1990. Parallel Algorithms for Shared-Memory Machines. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity . Elsevier and MIT Press, 869--942.

[44]

S. Rao Kosaraju and Arthur L. Delcher. 1988. Optimal Parallel Evaluation of Tree-Structured Computations by Raking. In VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, AWOC 88, Corfu, Greece, June 28 - July 1, 1988, Proceedings (Lecture Notes in Computer Science, Vol. 319), John H. Reif (Ed.). Springer, 101--110.

[45]

Chang Liu, Xiao Shaun Wang, Kartik Nayak, Yan Huang, and Elaine Shi. 2015. ObliVM: A Programming Framework for Secure Computation. In Proceedings of the 2015 IEEE Symposium on Security and Privacy. IEEE Computer Society, USA, 359--376.

Digital Library

[46]

Microsoft. [n.d.]. https://docs.microsoft.com/en-us/dotnet/standard/parallel-programming/task-parallel-library-tplredirectedfrom=MSDN .

[47]

Kartik Nayak, Xiao Shaun Wang, Stratis Ioannidis, Udi Weinsberg, Nina Taft, and Elaine Shi. 2015. GraphSC: Parallel Secure Computation Made Easy. In 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17--21, 2015. IEEE Computer Society, 377--394.

[48]

Oracle. [n.d.]. https://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html .

[49]

Seth Pettie and Vijaya Ramachandran. 2002. A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest. SIAM J. Comput., Vol. 31, 6 (2002), 1879--1895.

Digital Library

[50]

Vijaya Ramachandran and Elaine Shi. 2020. Data Oblivious Algorithms for Multicores. arxiv: 2008.00332 [cs.DC]

[51]

Elaine Shi. 2020. Path Oblivious Heap: Optimal and Practical Oblivious Priority Queue. In 2020 IEEE Symposium on Security and Privacy, SP 2020, San Francisco, CA, USA, May 18--21, 2020. IEEE, 842--858.

[52]

Elaine Shi, T.-H. Hubert Chan, Emil Stefanov, and Mingfei Li. 2011. Oblivious RAM with O((łog N)^3) Worst-Case Cost. In ASIACRYPT .

[53]

Yossi Shiloach and Uzi Vishkin. 1982. An O(log n) Parallel Connectivity Algorithm. J. Algorithms, Vol. 3, 1 (1982), 57--67.

[54]

Yuanzhong Xu, Weidong Cui, and Marcus Peinado. 2015. Controlled-Channel Attacks: Deterministic Side Channels for Untrusted Operating Systems. In Proceedings of the 2015 IEEE Symposium on Security and Privacy. IEEE Computer Society, USA, 640--656.

Digital Library

Cited By

Attrapadung NIsayama KSadakane KTozawa KLuo BLiao XXu JKirda ELie D(2024)Secure Parallel Computation with Oblivious State TransitionsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690315(3008-3022)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690315
Cao XLi YBogatov DLiu JRen K(2024)Secure and Practical Functional Dependency Discovery in Outsourced Databases2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00134(1645-1658)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00134
Tinoco AGao SShi ECalandrino JTroncoso C(2023)ENIGMAPProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620463(4033-4050)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620463
Show More Cited By

Recommendations

Resource Oblivious Sorting on Multicores
Special Issue on PPoPP 2015 and Regular Papers

We present a deterministic sorting algorithm, Sample, Partition, and Merge Sort (SPMS), that interleaves the partitioning of a sample sort with merging. Sequentially, it sorts n elements in O(nlog n) time cache-obliviously with an optimal number of ...
Randomized Shellsort: A Simple Data-Oblivious Sorting Algorithm

In this article, we describe a randomized Shellsort algorithm. This algorithm is a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in O(n log n) time and succeeds in sorting any given input permutation with very ...
Resource oblivious sorting on multicores
ICALP'10: Proceedings of the 37th international colloquium conference on Automata, languages and programming

We present a new deterministic sorting algorithm that interleaves the partitioning of a sample sort with merging. Sequentially, it sorts n elements in O(n log n) time cache-obliviously with an optimal number of cache misses. The parallel complexity (or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures

July 2021

463 pages

ISBN:9781450380706

DOI:10.1145/3409964

General Chair:
Kunal Agrawal
Washington University in St. Louis, USA
,
Program Chair:
Yossi Azar
Tel Aviv University, Israel

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF
Packard Fellowship
ONR

Conference

SPAA '21

Sponsor:

SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures

July 6 - 8, 2021

Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Upcoming Conference

SPAA '25

Sponsor:
sigact
sigact

37th ACM Symposium on Parallelism in Algorithms and Architectures

July 28 - August 1, 2025

Portland , OR , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
362
Total Downloads

Downloads (Last 12 months)130
Downloads (Last 6 weeks)15

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Attrapadung NIsayama KSadakane KTozawa KLuo BLiao XXu JKirda ELie D(2024)Secure Parallel Computation with Oblivious State TransitionsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690315(3008-3022)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690315
Cao XLi YBogatov DLiu JRen K(2024)Secure and Practical Functional Dependency Discovery in Outsourced Databases2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00134(1645-1658)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00134
Tinoco AGao SShi ECalandrino JTroncoso C(2023)ENIGMAPProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620463(4033-4050)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620463
Qiu LKellaris GMamoulis NNissim KKollios G(2023)Doquet: Differentially Oblivious Range and Join Queries with Private Data StructuresProceedings of the VLDB Endowment10.14778/3625054.362505516:13(4160-4173)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.14778/3625054.3625055
Sasy SJohnson AGoldberg IMeng WJensen CCremers CKirda E(2023)Waks-On/Waks-Off: Fast Oblivious Offline/Online Shuffling and Sorting with Waksman NetworksProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623133(3328-3342)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623133
Scheffler PZaruba FSchuiki FHoefler TBenini L(2023)Sparse Stream Semantic Registers: A Lightweight ISA Extension Accelerating General Sparse Linear AlgebraIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.332202934:12(3147-3161)Online publication date: 4-Oct-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3322029
Fernando RShi ESoni PVanjani NWaters B(2023)Non-Interactive Anonymous Router with Quasi-Linear Router ComputationTheory of Cryptography10.1007/978-3-031-48621-0_3(62-92)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48621-0_3
Mulligan DPetri GSpinale NStockwell GVincent H(2021)Confidential Computing—a brave new world2021 International Symposium on Secure and Private Execution Environment Design (SEED)10.1109/SEED51797.2021.00025(132-138)Online publication date: Sep-2021
https://doi.org/10.1109/SEED51797.2021.00025

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten