An Enhanced Distributed System to improve theTime Complexity of Binary Indexed Trees

Authors: Ahmed M. Elhabashy, A. Baes Mohamed, Abou El Nasr Mohamad

Abstract:

Distributed Computing Systems are usually considered the most suitable model for practical solutions of many parallel algorithms. In this paper an enhanced distributed system is presented to improve the time complexity of Binary Indexed Trees (BIT). The proposed system uses multi-uniform processors with identical architectures and a specially designed distributed memory system. The analysis of this system has shown that it has reduced the time complexity of the read query to O(Log(Log(N))), and the update query to constant complexity, while the naive solution has a time complexity of O(Log(N)) for both queries. The system was implemented and simulated using VHDL and Verilog Hardware Description Languages, with xilinx ISE 10.1, as the development environment and ModelSim 6.1c, similarly as the simulation tool. The simulation has shown that the overhead resulting by the wiring and communication between the system fragments could be fairly neglected, which makes it applicable to practically reach the maximum speed up offered by the proposed model.

Keywords: Binary Index Tree (BIT), Least Significant Bit (LSB), Parallel Adder (PA), Very High Speed Integrated Circuits HardwareDescription Language (VHDL), Distributed Parallel Computing System(DPCS).

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1061000

References:

[1] XST User Guide, Xilinx Inc.
[2] The Algorithm Design Manual. TELOS, The Electronic Library of Sciences, 1998.
[3] Digital Design: Principles and Practicese (4th Edition). Prentice Hall, 2005.
[4] Peter M. Fenwick. A new data structure for cumulative frequency tables. SOFTWAREPRACTICE AND EXPERIENCE, 1994.
[5] Ralph C. Hilzer Helen D. Karatza. Performance analysis of parallel job scheduling in distributed systems. Annual Simulation Symposium, 2003.
[6] TOPCODER Inc. Binary indexed trees . http://www.topcoder.com/tc?module=Statices, December 2008.
[7] TOPCODER Inc. Range minimum query and lowest common ancestor. http://www.topcoder.com/tc?module=Staticstor, January 2009.
[8] W. E. Johnston Q. M. Malluhi. Approaches for a reliable highperformance distributed-parallel storage system. High Performance Distributed Computing, 1996.
[9] Linda M.Wills Randall S. Janka. Specification and synthesis of real-time embedded distributed and parallel multiprocessor-based signal processing systems. International Conference on Compilers, Architecture and Synthesis for Embedded Systems, 2000
[10] Vijay K. Naik Vinod G. J. Peris, Mark S. Squillante. Analysis of the impact of memory in distributed parallel processing systems. Joint International Conference on Measurement and Modeling of Computer Systems, 1994.