The Power of Computing in Memory for Searching Algorithm

Year 2023, Volume: 19 Issue: 2, 71 - 89, 30.12.2023

Abdelkader Lazzem , Halit Öztekin

Abstract

This work focuses on the critical problem of search algorithm optimization to improve efficiency in a variety of applications within the field of computing. Through the utilization of technology's ongoing advancements, namely in the area of hardware acceleration, the research delves into different approaches meant to improve search algorithm performance. It presents a methodical comparison between the hardware-based BiCAM-based search algorithm and conventional software-based search algorithms like Sequential and Binary. The Field-Programmable Gate Array (FPGA), selected for its unmatched adaptability in hardware configurations, is used for implementation. By means of a thorough analysis, the study aims to identify the advantages, disadvantages, and complexity of these algorithms. The overall objective is to contribute to the continuing conversation in computer engineering and digital circuit design by providing nuanced insights into algorithm choices that are suited to particular application objectives. Essentially, the study explores the conditions of different FPGA-based search algorithms, offering a thorough comprehension to direct well-informed decisions for the best results in a range of applications. From the obtained results, it is evident that the BiCAM consumes more power and utilizes more resources but excels in terms of time complexity, making it a favorable trade-off in certain applications where speed is of greater importance.

Keywords

Search Operation, Field-programmable Gate Array (FPGA), Binary Search, Sequential Search, Binary Content Addressable Memory (BiCAM)

References

• [1] Cho, S., Martin, J.R., Xu R., Hammoud, M.H., Melhem, R. (2007). CA-RAM: A High-Performance Memory Substrate for Search-Intensive Applications. 2007 IEEE International Symposium on Performance Analysis of Systems & Software, 230-241.
• [2] Knuth, D.E. (1973). The Art of Computer Programming, Vol. 3 (Sorting and Searching), Addison-Wesley, USA
• [3] Schlesinger, R. (2009). Developing Real World Software, Jones & Bartlett Publishers
• [4] Mano, M.M. (1993). Computer System Architecture. Pearson, USA
• [5] Levitin, A. (2012). Introduction of the Design & Analysis of Algorithms. Addison-Wesley, USA
• [6] Cao, Y., Qi, H., Zhou, W., Kato, J., Li, K., Liu, X., Gui, J. (2018). Binary Hashing for Approximate Nearest Neighbor Search on Big Data: A Survey. IEEE Access 6, 2039-2054.
• [7] Irmayana, A., Sy, H., Paulus, Y.T., Aini, N., Aryasa, K.B. (2021). A Systematic Comparative Study of Linear, Binary and Interpolation Search Algorithms. 3rd International Conference on Cybernetics and Intelligent System (ICORIS) 1-5.
• [8] Sultana, N., Paira, S., Chandra, S., Alam, S.S. (2017). A brief study and analysis of different searching algorithms. Second International Conference on Electrical, Computer and Communication Technologies (ICECCT) 1-4.
• [9] Fukac, T., Korenek, J. (2019). Hash-based Pattern Matching for High Speed Networks. IEEE z22nd International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS) 1-5.
• [10] Balogun, G.B. () A Modified Linear Search Algorithm. African journal of computing & ic 12(2), 43 – 54.
• [11] Parmar, V. P., Kumbharana, C.K. (2015). Comparing Linear Search and Binary Search Algorithms to Search an Element from a Linear List Implemented through Static Array, Dynamic Array and Linked List. International Journal of Computer Applications,121 (3),13-17.
• [12] Arora, N., Bhasin, G., Sharma, N. (2014). Two way Linear Search Algorithm. International Journal of Computer Applications, 107, 6-8.
• [13] Nowak, R. (2008). Generalized binary search. 2008 46th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, 568-574.
• [14] Jacob, A. E., Ashodariya, N., Dhongade, A. (2017). Hybrid search algorithm: Combined linear and binary search algorithm," 2017 International Conference on Energy, Communication, Data Analytics and Soft Computing (ICECDS), Chennai, India.1543-1547.
• [15] Tiong, M. C. , Daniyal, H., Sulaiman, M. H. , Bakar, M. S. (2017). Binary search algorithm as maximum power point tracking technique for photovoltaic system under partial shaded conditions,2017 IEEE Conference on Energy Conversion (CENCON), Kuala Lumpur, Malaysia, 10-14.
• [16] Jin, Z., Finkel, H. (2020) Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform. 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3), GA, USA, 63-67.
• [17] Bennett, E.O., Ejiofor, V.E., Akpan, R.I. (2015). Efficient algorithm for binary search enhancement. 22(1).
• [18] Garzón, E., Yavits, L., Teman, A., Lanuzza, M. (2023). Approximate Content-Addressable Memories: A Review. Chips, 2(2),70-82.
• [19] Öztekin, H. (2022). BiCAM-based automated scoring system for digital logic circuit diagrams. Open Chemistry, 20(1), 1548-1556.
• [20] Garzón E, Lanuzza M, Teman A, Yavits L (2023) AM4: MRAM Crossbar Based CAM/TCAM/ACAM/AP for In-Memory Computing. IEEE Journal on Emerging and Selected Topics in Circuits and Systems 13(1), 408-421.
• [21] Lazzem, A., Öztekin, H., Pehlivan, İ. (2023). A case study: Understanding The Nature of Memories Architectures in FPGAs to Built-up Bi-CAM. Mühendislik Bilimleri ve Araştırmaları Dergisi, 5 (1), 47-56.
• [22] Öztekin, H., Lazzem, A. & Pehlivan, İ. (2023). Using FPGA-based content-addressable memory for mnemonics instruction searching in assembler design. J Supercomput 79, 17386–17418.
• [23] Boutros, A. , Betz, V. (2021). FPGA Architecture: Principles and Progression. IEEE Circuits and Systems Magazine, 21(2),4-29.
• [24] Trimberger, S. (1995). FPGA Technology: Past, Present, and Future”, ESSCIRC '95: Twenty-first European Solid-State Circuits Conference,12-15.
• [25] Kasivinayagam, G., Skanda, R., Burli, A.G., Jadon S., Sidhu,R. (2022) Hardware Description Language Enhancements for High-Level Synthesis of Hardware Accelerators, Advances in Computing and Data Sciences,1613,1-12.
• [26] Gandhare, S., Karthikeyan, B. (2019). Survey on FPGA Architecture and Recent Applications”, 2019 International Conference on Vision Towards Emerging Trends in Communication and Networking (ViTECoN),1-4.
• [27] Pagiamtzis, K., Sheikholeslami, A. (2006). Content-addressable memory (CAM) circuits and architectures: a tutorial and survey. IEEE Journal of Solid-State Circuits 41(3),712-727.
• [28] Sivakumar, SA., Swedha, A., Naveen, R. (2018) Survey of Content Addressable Memory. International Journal of Creative Research Thoughts 6(1):1516-1526.
• [29] Jothi, D., Sivakumar, R. (2018) Design and Analysis of Power Efficient Binary Content Addressable Memory (PEBCAM) Core Cells”, Circuits, Systems, and Signal Processing, 37(6),1422–1451.
• [30] Zackriya, M. V., Kittur, H. M. (2016). Precharge-Free Low-Power Content-Addressable Memory, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 24(8),2614-2621.
• [31] Wasmir, S.H., Venkata, T.M. , Sandeep, S., Anup, D. (2020). Low-Power Content Addressable Memory Design using Two-Layer P-N Match-Line Control and Sensing.Integration, 75,73-84.
• [32] Chang, Y.J., Tsai,K. , Cheng, Y.C., Lu, M.R. (2020). Low-power ternary content-addressable memory design based on a voltage self-controlled fin field-effect transistor segment. Computers & Electrical Engineering 81:106528.
• [33] Jiang, S., Yan, P., Sridhar, R. (2015). A high speed and low power content- addressable memory (CAM) using pipelined scheme. 2015 28th IEEE International System-on-Chip Conference, 345-349.
• [34] Aremu, B. (2023). Introduction to Algorithms and Data Structures: A Solid Foundation for the Real World of Machine Learning and Data Analytics. Nigeria: Ojula Technology Innovations.
• [35] Sultana, N., Paira, S., Chandra, S., Alam, S. K. S. (2017). A brief study and analysis of different searching algorithms," 2017 Second International Conference on Electrical, Computer and Communication Technologies (ICECCT), Coimbatore, India, 1-4.
• [36] Sanders, P., Mehlhorn, K., Dietzfelbinger, M., Dementiev, R. (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Germany: Springer International Publishing.
• [37] Search Algorithm: Fundamentals and Applications. (2023). One Billion Knowledgeable.
• [38] Irfan, M, Sanka, A.I., Ullah, Z., Cheung, R.C.C. (2021). Reconfigurable content-addressable memory (CAM) on FPGAs: A tutorial and survey, Future Generation Computer Systems, 128, 451-465, 2021.
• [39] Pagiamtzis, K., Sheikholeslami, A. (2006). Content-addressable memory (CAM) circuits and architectures: a tutorial and survey. IEEE Journal of Solid-State Circuits 41(3):712-727.
• [40] Sipser, M. (2012). Introduction to the Theory of Computation”, Cengage Learning .
• [41] Chatterjee, A., Kiao, U. (2021) Time Complexity Analysis (Coding Interviews: Algorithm and Data Structure Proficiency), Independently published.