{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:03Z","timestamp":1750306683872,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,3,31]],"date-time":"2015-03-31T00:00:00Z","timestamp":1427760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Deutsche Forschungsgemeinschaft (DFG) within the Collaborative Research Center SFB 876 \u201cProviding Information by Resource-Constrained Analysis.\u201d"},{"name":"Enterprise Computing Center (ECC) at ETH Z\u00fcrich"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2015,4,17]]},"abstract":"<jats:p>Parallelism is currently seen as a mechanism to minimize the impact of the power and heat dissipation problems encountered in modern hardware. Data parallelism\u2014based on partitioning the data\u2014and pipeline parallelism\u2014based on partitioning the computation\u2014are the two main approaches to leverage parallelism on a wide range of hardware platforms.<\/jats:p>\n          <jats:p>\n            Unfortunately, not all data processing problems are susceptible to either of those strategies. An example is the\n            <jats:italic>skyline<\/jats:italic>\n            operator [B\u00f6rzs\u00f6nyi et al. 2001], which computes the set of Pareto-optimal points within a multidimensional dataset. Existing approaches to parallelize the skyline operator are based on data parallelism. As a result, they suffer from a high overhead when merging intermediate results because of the lack of a global view of the problem inherent to partitioning the input data.\n          <\/jats:p>\n          <jats:p>\n            In this article, we show how to combine pipeline with data parallelism on a Field-Programmable Gate Array (FPGA) for a more efficient utilization of the available hardware parallelism. As we show in our experiments, skyline computation using our proposed technique scales linearly with the number of processing elements, and the performance we achieve on a rather small FPGA is comparable to that of a 64-core high-end server running a state-of-the-art\n            <jats:italic>data parallel<\/jats:italic>\n            implementation of\n            <jats:italic>skyline<\/jats:italic>\n            [Park et al. 2009].\n          <\/jats:p>\n          <jats:p>\n            The proposed approach to parallelize the skyline operator can be generalized to a wider range of data processing problems. We demonstrate this through a novel, highly parallel data structure, a\n            <jats:italic>shifter list<\/jats:italic>\n            , that can be efficiently implemented on an FPGA. The resulting template is easy to parametrize to implement a variety of computationally intensive operators such as\n            <jats:italic>frequent items<\/jats:italic>\n            ,\n            <jats:italic>\n              <jats:italic>n<\/jats:italic>\n              -closest pairs\n            <\/jats:italic>\n            , or\n            <jats:italic>K-means<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/2629551","type":"journal-article","created":{"date-parts":[[2015,4,3]],"date-time":"2015-04-03T20:29:44Z","timestamp":1428092984000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Parallelizing Data Processing on FPGAs with Shifter Lists"],"prefix":"10.1145","volume":"8","author":[{"given":"Louis","family":"Woods","sequence":"first","affiliation":[{"name":"Systems Group, Department of Computer Science, ETH Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gustavo","family":"Alonso","sequence":"additional","affiliation":[{"name":"Systems Group, Department of Computer Science, ETH Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Teubner","sequence":"additional","affiliation":[{"name":"DBIS Group, Department of Computer Science, TU Dortmund University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,3,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA\u201909)","author":"Bittner Ray","year":"2009","unstructured":"Ray Bittner . 2009 . The speedy DDR2 controller for FPGAs . In Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA\u201909) . Ray Bittner. 2009. The speedy DDR2 controller for FPGAs. In Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA\u201909)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1941487.1941507"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1893173.1893176"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950413.1950435"},{"key":"e_1_2_1_6_1","unstructured":"Convey Computer. 2014. Convey HC-2. Retrieved from http:\/\/www.conveycomputer.com.  Convey Computer. 2014. Convey HC-2. Retrieved from http:\/\/www.conveycomputer.com."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2012.18"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2010.29"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000064.2000108"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083622"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1450095.1450105"},{"key":"e_1_2_1_13_1","unstructured":"IBM. 2014. IBM Netezza Data Warehouse Appliances. Retrieved from http:\/\/www.ibm.com\/software\/data\/netezza.  IBM. 2014. IBM Netezza Data Warehouse Appliances. Retrieved from http:\/\/www.ibm.com\/software\/data\/netezza."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2011.27"},{"key":"e_1_2_1_15_1","volume-title":"IFIP Congress.","author":"Kahn Gilles","year":"1974","unstructured":"Gilles Kahn . 1974 . The semantics of simple language for parallel programming . In IFIP Congress. Gilles Kahn. 1974. The semantics of simple language for parallel programming. In IFIP Congress."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950413.1950427"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767899"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.42"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2011.18"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978542.1978558"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370816.2370874"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447856"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Workshop on Recommendation and Personalization in eCommerce (RPEC\u201902)","author":"Torlone Riccardo","year":"2002","unstructured":"Riccardo Torlone and Paolo Ciaccia . 2002 . Which are my preferred items . In Proceedings of the Workshop on Recommendation and Personalization in eCommerce (RPEC\u201902) . Riccardo Torlone and Paolo Ciaccia. 2002. Which are my preferred items. In Proceedings of the Workshop on Recommendation and Personalization in eCommerce (RPEC\u201902)."}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629551","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629551","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:18Z","timestamp":1750230078000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629551"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,31]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,4,17]]}},"alternative-id":["10.1145\/2629551"],"URL":"https:\/\/doi.org\/10.1145\/2629551","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2015,3,31]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}