Showing 1–18 of 18 results for author: Patkar, S

Resistive Memory for Computing and Security: Algorithms, Architectures, and Platforms

Authors: Simranjeet Singh, Farhad Merchant, Sachin Patkar

Abstract: Resistive random-access memory (RRAM) is gaining popularity due to its ability to offer computing within the memory and its non-volatile nature. The unique properties of RRAM, such as binary switching, multi-state switching, and device variations, can be leveraged to design novel techniques and algorithms. This thesis proposes a technique for utilizing RRAM devices in three major directions: i) di… ▽ More Resistive random-access memory (RRAM) is gaining popularity due to its ability to offer computing within the memory and its non-volatile nature. The unique properties of RRAM, such as binary switching, multi-state switching, and device variations, can be leveraged to design novel techniques and algorithms. This thesis proposes a technique for utilizing RRAM devices in three major directions: i) digital logic implementation, ii) multi-valued computing, and iii) hardware security primitive design. We proposed new algorithms and architectures and conducted \textit{experimental studies} on each implementation. Moreover, we developed the electronic design automation framework and hardware platforms to facilitate these experiments. △ Less

Submitted 4 July, 2024; originally announced July 2024.

Comments: Accepted as PhD Forum at VLSI-SoC 2024

In-Memory Mirroring: Cloning Without Reading

Authors: Simranjeet Singh, Ankit Bende, Chandan Kumar Jha, Vikas Rana, Rolf Drechsler, Sachin Patkar, Farhad Merchant

Abstract: In-memory computing (IMC) has gained significant attention recently as it attempts to reduce the impact of memory bottlenecks. Numerous schemes for digital IMC are presented in the literature, focusing on logic operations. Often, an application's description has data dependencies that must be resolved. Contemporary IMC architectures perform read followed by write operations for this purpose, which… ▽ More In-memory computing (IMC) has gained significant attention recently as it attempts to reduce the impact of memory bottlenecks. Numerous schemes for digital IMC are presented in the literature, focusing on logic operations. Often, an application's description has data dependencies that must be resolved. Contemporary IMC architectures perform read followed by write operations for this purpose, which results in performance and energy penalties. To solve this fundamental problem, this paper presents in-memory mirroring (IMM). IMM eliminates the need for read and write-back steps, thus avoiding energy and performance penalties. Instead, we perform data movement within memory, involving row-wise and column-wise data transfers. Additionally, the IMM scheme enables parallel cloning of entire row (word) with a complexity of $\mathcal{O}(1)$. Moreover, our analysis of the energy consumption of the proposed technique using resistive random-access memory crossbar and experimentally validated JART VCM v1b model. The IMM increases energy efficiency and shows 2$\times$ performance improvement compared to conventional data movement methods. △ Less

Submitted 4 July, 2024; v1 submitted 3 July, 2024; originally announced July 2024.

Comments: Accepted in IFIP/IEEE VLSI-SoC 2024

Python-based DSL for generating Verilog model of Synchronous Digital Circuits

Authors: Mandar Datar, Dhruva S. Hegde, Vendra Durga Prasad, Manish Prajapati, Neralla Manikanta, Devansh Gupta, Janampalli Pavanija, Pratyush Pare, Akash, Shivam Gupta, Sachin B. Patkar

Abstract: We have designed a Python-based Domain Specific Language (DSL) for modeling synchronous digital circuits. In this DSL, hardware is modeled as a collection of transactions -- running in series, parallel, and loops. When the model is executed by a Python interpreter, synthesizable and behavioural Verilog is generated as output, which can be integrated with other RTL designs or directly used for FPGA… ▽ More We have designed a Python-based Domain Specific Language (DSL) for modeling synchronous digital circuits. In this DSL, hardware is modeled as a collection of transactions -- running in series, parallel, and loops. When the model is executed by a Python interpreter, synthesizable and behavioural Verilog is generated as output, which can be integrated with other RTL designs or directly used for FPGA and ASIC flows. In this paper, we describe - 1) the language (DSL), which allows users to express computation in series/parallel/loop constructs, with explicit cycle boundaries, 2) the internals of a simple Python implementation to produce synthesizable Verilog, and 3) several design examples and case studies for applications in post-quantum cryptography, stereo-vision, digital signal processing and optimization techniques. In the end, we list ideas to extend this framework. △ Less

Submitted 13 June, 2024; originally announced June 2024.

Comments: 9 pages, 13 figures

Experimental Validation of Memristor-Aided Logic Using 1T1R TaOx RRAM Crossbar Array

Authors: Ankit Bende, Simranjeet Singh, Chandan Kumar Jha, Tim Kempen, Felix Cüppers, Christopher Bengel, Andre Zambanini, Dennis Nielinger, Sachin Patkar, Rolf Drechsler, Rainer Waser, Farhad Merchant, Vikas Rana

Abstract: Memristor-aided logic (MAGIC) design style holds a high promise for realizing digital logic-in-memory functionality. The ability to implement a specific gate in a MAGIC design style hinges on the SET-to-RESET threshold ratio. The TaOx memristive devices exhibit distinct SET-to-RESET ratios, enabling the implementation of OR and NOT operations. As the adoption of the MAGIC design style gains moment… ▽ More Memristor-aided logic (MAGIC) design style holds a high promise for realizing digital logic-in-memory functionality. The ability to implement a specific gate in a MAGIC design style hinges on the SET-to-RESET threshold ratio. The TaOx memristive devices exhibit distinct SET-to-RESET ratios, enabling the implementation of OR and NOT operations. As the adoption of the MAGIC design style gains momentum, it becomes crucial to understand the breakdown of energy consumption in the various phases of its operation. This paper presents experimental demonstrations of the OR and NOT gates on a 1T1R crossbar array. Additionally, it provides insights into the energy distribution for performing these operations at different stages. Through our experiments across different gates, we found that the energy consumption is dominated by initialization in the MAGIC design style. The energy split-up is 14.8%, 85%, and 0.2% for execution, initialization, and read operations respectively. △ Less

Submitted 16 October, 2023; originally announced October 2023.

Comments: Accepted in VLSID 2024

MemSPICE: Automated Simulation and Energy Estimation Framework for MAGIC-Based Logic-in-Memory

Authors: Simranjeet Singh, Chandan Kumar Jha, Ankit Bende, Vikas Rana, Sachin Patkar, Rolf Drechsler, Farhad Merchant

Abstract: Existing logic-in-memory (LiM) research is limited to generating mappings and micro-operations. In this paper, we present~\emph{MemSPICE}, a novel framework that addresses this gap by automatically generating both the netlist and testbench needed to evaluate the LiM on a memristive crossbar. MemSPICE goes beyond conventional approaches by providing energy estimation scripts to calculate the precis… ▽ More Existing logic-in-memory (LiM) research is limited to generating mappings and micro-operations. In this paper, we present~\emph{MemSPICE}, a novel framework that addresses this gap by automatically generating both the netlist and testbench needed to evaluate the LiM on a memristive crossbar. MemSPICE goes beyond conventional approaches by providing energy estimation scripts to calculate the precise energy consumption of the testbench at the SPICE level. We propose an automated framework that utilizes the mapping obtained from the SIMPLER tool to perform accurate energy estimation through SPICE simulations. To the best of our knowledge, no existing framework is capable of generating a SPICE netlist from a hardware description language. By offering a comprehensive solution for SPICE-based netlist generation, testbench creation, and accurate energy estimation, MemSPICE empowers researchers and engineers working on memristor-based LiM to enhance their understanding and optimization of energy usage in these systems. Finally, we tested the circuits from the ISCAS'85 benchmark on MemSPICE and conducted a detailed energy analysis. △ Less

Submitted 9 September, 2023; originally announced September 2023.

Comments: Accepted in ASP-DAC 2024

Should We Even Optimize for Execution Energy? Rethinking Mapping for MAGIC Design Style

Authors: Simranjeet Singh, Chandan Kumar Jha, Ankit Bende, Phrangboklang Lyngton Thangkhiew, Vikas Rana, Sachin Patkar, Rolf Drechsler, Farhad Merchant

Abstract: Memristor-based logic-in-memory (LiM) has become popular as a means to overcome the von Neumann bottleneck in traditional data-intensive computing. Recently, the memristor-aided logic (MAGIC) design style has gained immense traction for LiM due to its simplicity. However, understanding the energy distribution during the design of logic operations within the memristive memory is crucial in assessin… ▽ More Memristor-based logic-in-memory (LiM) has become popular as a means to overcome the von Neumann bottleneck in traditional data-intensive computing. Recently, the memristor-aided logic (MAGIC) design style has gained immense traction for LiM due to its simplicity. However, understanding the energy distribution during the design of logic operations within the memristive memory is crucial in assessing such an implementation's significance. The current energy estimation methods rely on coarse-grained techniques, which underestimate the energy consumption of MAGIC-styled operations performed on a memristor crossbar. To address this issue, we analyze the energy breakdown in MAGIC operations and propose a solution that utilizes mapping from the SIMPLER MAGIC tool to achieve accurate energy estimation through SPICE simulations. In contrast to existing research that primarily focuses on optimizing execution energy, our findings reveal that the memristor's initialization energy in the MAGIC design style is, on average, 68x higher. We demonstrate that this initialization energy significantly dominates the overall energy consumption. By highlighting this aspect, we aim to redirect the attention of designers towards developing algorithms and strategies that prioritize optimizations in initializations rather than execution for more effective energy savings. △ Less

Submitted 7 July, 2023; originally announced July 2023.

Comments: Accepted to published in IEEE EMBEDDED SYSTEMS LETTER

IMBUE: In-Memory Boolean-to-CUrrent Inference ArchitecturE for Tsetlin Machines

Authors: Omar Ghazal, Simranjeet Singh, Tousif Rahman, Shengqi Yu, Yujin Zheng, Domenico Balsamo, Sachin Patkar, Farhad Merchant, Fei Xia, Alex Yakovlev, Rishad Shafik

Abstract: In-memory computing for Machine Learning (ML) applications remedies the von Neumann bottlenecks by organizing computation to exploit parallelism and locality. Non-volatile memory devices such as Resistive RAM (ReRAM) offer integrated switching and storage capabilities showing promising performance for ML applications. However, ReRAM devices have design challenges, such as non-linear digital-analog… ▽ More In-memory computing for Machine Learning (ML) applications remedies the von Neumann bottlenecks by organizing computation to exploit parallelism and locality. Non-volatile memory devices such as Resistive RAM (ReRAM) offer integrated switching and storage capabilities showing promising performance for ML applications. However, ReRAM devices have design challenges, such as non-linear digital-analog conversion and circuit overheads. This paper proposes an In-Memory Boolean-to-Current Inference Architecture (IMBUE) that uses ReRAM-transistor cells to eliminate the need for such conversions. IMBUE processes Boolean feature inputs expressed as digital voltages and generates parallel current paths based on resistive memory states. The proportional column current is then translated back to the Boolean domain for further digital processing. The IMBUE architecture is inspired by the Tsetlin Machine (TM), an emerging ML algorithm based on intrinsically Boolean logic. The IMBUE architecture demonstrates significant performance improvements over binarized convolutional neural networks and digital TM in-memory implementations, achieving up to a 12.99x and 5.28x increase, respectively. △ Less

Submitted 22 May, 2023; originally announced May 2023.

Comments: Accepted at ACM/IEEE International Symposium on Low Power Electronics and Design 2023 (ISLPED 2023)

Finite State Automata Design using 1T1R ReRAM Crossbar

Authors: Simranjeet Singh, Omar Ghazal, Chandan Kumar Jha, Vikas Rana, Rolf Drechsler, Rishad Shafik, Alex Yakovlev, Sachin Patkar, Farhad Merchant

Abstract: Data movement costs constitute a significant bottleneck in modern machine learning (ML) systems. When combined with the computational complexity of algorithms, such as neural networks, designing hardware accelerators with low energy footprint remains challenging. Finite state automata (FSA) constitute a type of computation model used as a low-complexity learning unit in ML systems. The implementat… ▽ More Data movement costs constitute a significant bottleneck in modern machine learning (ML) systems. When combined with the computational complexity of algorithms, such as neural networks, designing hardware accelerators with low energy footprint remains challenging. Finite state automata (FSA) constitute a type of computation model used as a low-complexity learning unit in ML systems. The implementation of FSA consists of a number of memory states. However, FSA can be in one of the states at a given time. It switches to another state based on the present state and input to the FSA. Due to its natural synergy with memory, it is a promising candidate for in-memory computing for reduced data movement costs. This work focuses on a novel FSA implementation using resistive RAM (ReRAM) for state storage in series with a CMOS transistor for biasing controls. We propose using multi-level ReRAM technology capable of transitioning between states depending on bias pulse amplitude and duration. We use an asynchronous control circuit for writing each ReRAM-transistor cell for the on-demand switching of the FSA. We investigate the impact of the device-to-device and cycle-to-cycle variations on the cell and show that FSA transitions can be seamlessly achieved without degradation of performance. Through extensive experimental evaluation, we demonstrate the implementation of FSA on 1T1R ReRAM crossbar. △ Less

Submitted 30 June, 2023; v1 submitted 26 April, 2023; originally announced April 2023.

Comments: Accepted by 21st IEEE Interregional NEWCAS Conference 2023 (NEWCAS 2023)

Integrated Architecture for Neural Networks and Security Primitives using RRAM Crossbar

Authors: Simranjeet Singh, Furqan Zahoor, Gokulnath Rajendran, Vikas Rana, Sachin Patkar, Anupam Chattopadhyay, Farhad Merchant

Abstract: This paper proposes an architecture that integrates neural networks (NNs) and hardware security modules using a single resistive random access memory (RRAM) crossbar. The proposed architecture enables using a single crossbar to implement NN, true random number generator (TRNG), and physical unclonable function (PUF) applications while exploiting the multi-state storage characteristic of the RRAM c… ▽ More This paper proposes an architecture that integrates neural networks (NNs) and hardware security modules using a single resistive random access memory (RRAM) crossbar. The proposed architecture enables using a single crossbar to implement NN, true random number generator (TRNG), and physical unclonable function (PUF) applications while exploiting the multi-state storage characteristic of the RRAM crossbar for the vector-matrix multiplication operation required for the implementation of NN. The TRNG is implemented by utilizing the crossbar's variation in device switching thresholds to generate random bits. The PUF is implemented using the same crossbar initialized as an entropy source for the TRNG. Additionally, the weights locking concept is introduced to enhance the security of NNs by preventing unauthorized access to the NN weights. The proposed architecture provides flexibility to configure the RRAM device in multiple modes to suit different applications. It shows promise in achieving a more efficient and compact design for the hardware implementation of NNs and security primitives. △ Less

Submitted 1 May, 2023; v1 submitted 26 April, 2023; originally announced April 2023.

Hardware Security Primitives using Passive RRAM Crossbar Array: Novel TRNG and PUF Designs

Authors: Simranjeet Singh, Furqan Zahoor, Gokulnath Rajendran, Sachin Patkar, Anupam Chattopadhyay, Farhad Merchant

Abstract: With rapid advancements in electronic gadgets, the security and privacy aspects of these devices are significant. For the design of secure systems, physical unclonable function (PUF) and true random number generator (TRNG) are critical hardware security primitives for security applications. This paper proposes novel implementations of PUF and TRNGs on the RRAM crossbar structure. Firstly, two tech… ▽ More With rapid advancements in electronic gadgets, the security and privacy aspects of these devices are significant. For the design of secure systems, physical unclonable function (PUF) and true random number generator (TRNG) are critical hardware security primitives for security applications. This paper proposes novel implementations of PUF and TRNGs on the RRAM crossbar structure. Firstly, two techniques to implement the TRNG in the RRAM crossbar are presented based on write-back and 50% switching probability pulse. The randomness of the proposed TRNGs is evaluated using the NIST test suite. Next, an architecture to implement the PUF in the RRAM crossbar is presented. The initial entropy source for the PUF is used from TRNGs, and challenge-response pairs (CRPs) are collected. The proposed PUF exploits the device variations and sneak-path current to produce unique CRPs. We demonstrate, through extensive experiments, reliability of 100%, uniqueness of 47.78%, uniformity of 49.79%, and bit-aliasing of 48.57% without any post-processing techniques. Finally, the design is compared with the literature to evaluate its implementation efficiency, which is clearly found to be superior to the state-of-the-art. △ Less

Submitted 7 November, 2022; originally announced November 2022.

Comments: To appear at ASP-DAC 2023

PA-PUF: A Novel Priority Arbiter PUF

Authors: Simranjeet Singh, Srinivasu Bodapati, Sachin Patkar, Rainer Leupers, Anupam Chattopadhyay, Farhad Merchant

Abstract: This paper proposes a 3-input arbiter-based novel physically unclonable function (PUF) design. Firstly, a 3-input priority arbiter is designed using a simple arbiter, two multiplexers (2:1), and an XOR logic gate. The priority arbiter has an equal probability of 0's and 1's at the output, which results in excellent uniformity (49.45%) while retrieving the PUF response. Secondly, a new PUF design b… ▽ More This paper proposes a 3-input arbiter-based novel physically unclonable function (PUF) design. Firstly, a 3-input priority arbiter is designed using a simple arbiter, two multiplexers (2:1), and an XOR logic gate. The priority arbiter has an equal probability of 0's and 1's at the output, which results in excellent uniformity (49.45%) while retrieving the PUF response. Secondly, a new PUF design based on priority arbiter PUF (PA-PUF) is presented. The PA-PUF design is evaluated for uniqueness, non-linearity, and uniformity against the standard tests. The proposed PA-PUF design is configurable in challenge-response pairs through an arbitrary number of feed-forward priority arbiters introduced to the design. We demonstrate, through extensive experiments, reliability of 100% after performing the error correction techniques and uniqueness of 49.63%. Finally, the design is compared with the literature to evaluate its implementation efficiency, where it is clearly found to be superior compared to the state-of-the-art. △ Less

Submitted 21 July, 2022; originally announced July 2022.

Single Storage Semi-Global Matching for Real Time Depth Processing

Authors: Prathmesh Sawant, Yashwant Temburu, Mandar Datar, Imran Ahmed, Vinayak Shriniwas, Sachin Patkar

Abstract: Depth-map is the key computation in computer vision and robotics. One of the most popular approach is via computation of disparity-map of images obtained from Stereo Camera. Semi Global Matching (SGM) method is a popular choice for good accuracy with reasonable computation time. To use such compute-intensive algorithms for real-time applications such as for autonomous aerial vehicles, blind Aid, e… ▽ More Depth-map is the key computation in computer vision and robotics. One of the most popular approach is via computation of disparity-map of images obtained from Stereo Camera. Semi Global Matching (SGM) method is a popular choice for good accuracy with reasonable computation time. To use such compute-intensive algorithms for real-time applications such as for autonomous aerial vehicles, blind Aid, etc. acceleration using GPU, FPGA is necessary. In this paper, we show the design and implementation of a stereo-vision system, which is based on FPGA-implementation of More Global Matching(MGM). MGM is a variant of SGM. We use 4 paths but store a single cumulative cost value for a corresponding pixel. Our stereo-vision prototype uses Zedboard containing an ARM-based Zynq-SoC, ZED-stereo-camera / ELP stereo-camera / Intel RealSense D435i, and VGA for visualization. The power consumption attributed to the custom FPGA-based acceleration of disparity map computation required for depth-map is just 0.72 watt. The update rate of the disparity map is realistic 10.5 fps. △ Less

Submitted 7 July, 2020; originally announced July 2020.

Comments: 10 pages, Published in National Conference on Computer Vision, Pattern Recognition, Image Processing and Graphics(NCVPRIPG) 2019

CLARINET: A RISC-V Based Framework for Posit Arithmetic Empiricism

Authors: Niraj Sharma, Riya Jain, Madhumita Mohan, Sachin Patkar, Rainer Leupers, Nikhil Rishiyur, Farhad Merchant

Abstract: Many engineering and scientific applications require high precision arithmetic. IEEE~754-2008 compliant (floating-point) arithmetic is the de facto standard for performing these computations. Recently, posit arithmetic has been proposed as a drop-in replacement for floating-point arithmetic. The posit\texttrademark data representation and arithmetic claim several absolute advantages over the float… ▽ More Many engineering and scientific applications require high precision arithmetic. IEEE~754-2008 compliant (floating-point) arithmetic is the de facto standard for performing these computations. Recently, posit arithmetic has been proposed as a drop-in replacement for floating-point arithmetic. The posit\texttrademark data representation and arithmetic claim several absolute advantages over the floating-point format and arithmetic, including higher dynamic range, better accuracy, and superior performance-area trade-offs. However, there does not exist any accessible, holistic framework that facilitates the validation of these claims of posit arithmetic, especially when the claims involve long accumulations (quire). In this paper, we present a consolidated general-purpose processor-based framework to support posit arithmetic empiricism. The end-users of the framework have the liberty to seamlessly experiment with their applications using posit and floating-point arithmetic since the framework is designed for the two number systems to coexist. Melodica is a posit arithmetic core that implements parametric fused operations that uniquely involve the quire data type. Clarinet is a Melodica-enabled processor based on the RISC-V ISA. To the best of our knowledge, this is the first-ever integration of quire with a RISC-V core. To show the effectiveness of the Clarinet platform, we perform an extensive application study and benchmark some of the common linear algebra and computer vision kernels. We emulate Clarinet on a Xilinx FPGA and present utilization and timing data. Clarinet and Melodica remain actively under development and is available in open-source for posit arithmetic empiricism. △ Less

Submitted 27 October, 2021; v1 submitted 30 May, 2020; originally announced June 2020.

Framework for Application Mapping over Packet-Switched Network of FPGAs: Case Studies

Authors: Vinay B. Y. Kumar, Pinalkumar Engineer, Mandar Datar, Yatish Turakhia, Saurabh Agarwal, Sanket Diwale, Sachin B. Patkar

Abstract: The algorithm-to-hardware High-level synthesis (HLS) tools today are purported to produce hardware comparable in quality to handcrafted designs, particularly with user directive driven or domains specific HLS. However, HLS tools are not readily equipped for when an application/algorithm needs to scale. We present a (work-in-progress) semi-automated framework to map applications over a packet-switc… ▽ More The algorithm-to-hardware High-level synthesis (HLS) tools today are purported to produce hardware comparable in quality to handcrafted designs, particularly with user directive driven or domains specific HLS. However, HLS tools are not readily equipped for when an application/algorithm needs to scale. We present a (work-in-progress) semi-automated framework to map applications over a packet-switched network of modules (single FPGA) and then to seamlessly partition such a network over multiple FPGAs over quasi-serial links. We illustrate the framework through three application case studies: LDPC Decoding, Particle Filter based Object Tracking, and Matrix Vector Multiplication over GF(2). Starting with high-level representations of each case application, we first express them in an intermediate message passing formulation, a model of communicating processing elements. Once the processing elements are identified, these are either handcrafted or realized using HLS. The rest of the flow is automated where the processing elements are plugged on to a configurable network-on-chip (CONNECT) topology of choice, followed by partitioning the 'on-chip' links to work seamlessly across chips/FPGAs. △ Less

Submitted 27 August, 2015; originally announced August 2015.

Comments: Presented at Second International Workshop on FPGAs for Software Programmers (FSP 2015) (arXiv:1508.06320)

Report number: FSP/2015/05

Expander-like Codes based on Finite Projective Geometry

Authors: Swadesh Choudhary, Hrishikesh Sharma, B. S. Adiga, Sachin Patkar

Abstract: We present a novel error correcting code and decoding algorithm which have construction similar to expander codes. The code is based on a bipartite graph derived from the subsumption relations of finite projective geometry, and Reed-Solomon codes as component codes. We use a modified version of well-known Zemor's decoding algorithm for expander codes, for decoding our codes. By derivation of geome… ▽ More We present a novel error correcting code and decoding algorithm which have construction similar to expander codes. The code is based on a bipartite graph derived from the subsumption relations of finite projective geometry, and Reed-Solomon codes as component codes. We use a modified version of well-known Zemor's decoding algorithm for expander codes, for decoding our codes. By derivation of geometric bounds rather than eigenvalue bounds, it has been proved that for practical values of the code rate, the random error correction capability of our codes is much better than those derived for previously studied graph codes, including Zemor's bound. MATLAB simulations further reveal that the average case performance of this code is 10 times better than these geometric bounds obtained, in almost 99% of the test cases. By exploiting the symmetry of projective space lattices, we have designed a corresponding decoder that has optimal throughput. The decoder design has been prototyped on Xilinx Virtex 5 FPGA. The codes are designed for potential applications in secondary storage media. As an application, we also discuss usage of these codes to improve the burst error correction capability of CD-ROM decoder. △ Less

Submitted 16 September, 2012; originally announced September 2012.

A Design Methodology for Folded, Pipelined Architectures in VLSI Applications using Projective Space Lattices

Authors: Hrishikesh Sharma, Sachin Patkar

Abstract: Semi-parallel, or folded, VLSI architectures are used whenever hardware resources need to be saved at design time. Most recent applications that are based on Projective Geometry (PG) based balanced bipartite graph also fall in this category. In this paper, we provide a high-level, top-down design methodology to design optimal semi-parallel architectures for applications, whose Data Flow Graph (DFG… ▽ More Semi-parallel, or folded, VLSI architectures are used whenever hardware resources need to be saved at design time. Most recent applications that are based on Projective Geometry (PG) based balanced bipartite graph also fall in this category. In this paper, we provide a high-level, top-down design methodology to design optimal semi-parallel architectures for applications, whose Data Flow Graph (DFG) is based on PG bipartite graph. Such applications have been found e.g. in error-control coding and matrix computations. Unlike many other folding schemes, the topology of connections between physical elements does not change in this methodology. Another advantage is the ease of implementation. To lessen the throughput loss due to folding, we also incorporate a multi-tier pipelining strategy in the design methodology. The design methodology has been verified by implementing a synthesis tool in C++, which has been verified as well. The tool is publicly available. Further, a complete decoder was manually protototyped before the synthesis tool design, to verify all the algorithms evolved in this paper, towards various steps of refinement. Another specific high-performance design of an LDPC decoder based on this methodology was worked out in past, and has been patented as well. △ Less

Submitted 4 August, 2012; v1 submitted 19 August, 2011; originally announced August 2011.

Comments: Submitted to Elsevier Journal of Microprocessors and Microsystems: Embedded Hardware Design

Finite Projective Geometry based Fast, Conflict-free Parallel Matrix Computations

Authors: Shreeniwas Sapre, Hrishikesh Sharma, Abhishek Patil, B. S. Adiga, Sachin Patkar

Abstract: Matrix computations, especially iterative PDE solving (and the sparse matrix vector multiplication subproblem within) using conjugate gradient algorithm, and LU/Cholesky decomposition for solving system of linear equations, form the kernel of many applications, such as circuit simulators, computational fluid dynamics or structural analysis etc. The problem of designing approaches for parallelizing… ▽ More Matrix computations, especially iterative PDE solving (and the sparse matrix vector multiplication subproblem within) using conjugate gradient algorithm, and LU/Cholesky decomposition for solving system of linear equations, form the kernel of many applications, such as circuit simulators, computational fluid dynamics or structural analysis etc. The problem of designing approaches for parallelizing these computations, to get good speedups as much as possible as per Amdahl's law, has been continuously researched upon. In this paper, we discuss approaches based on the use of finite projective geometry graphs for these two problems. For the problem of conjugate gradient algorithm, the approach looks at an alternative data distribution based on projective-geometry concepts. It is proved that this data distribution is an optimal data distribution for scheduling the main problem of dense matrix-vector multiplication. For the problem of parallel LU/Cholesky decomposition of general matrices, the approach is motivated by the recently published scheme for interconnects of distributed systems, perfect difference networks. We find that projective-geometry based graphs indeed offer an exciting way of parallelizing these computations, and in fact many others. Moreover, their applications ranges from architectural ones (interconnect choice) to algorithmic ones (data distributions). △ Less

Submitted 5 July, 2011; originally announced July 2011.

Comments: 32 pages, to be submitted to some distributed and parallel computing journal

Optimal Folding of Data Flow Graphs based on Finite Projective Geometry using Lattice Embedding

Authors: Swadesh Choudhary, Hrishikesh Sharma, Sachin Patkar

Abstract: A number of computations exist, especially in area of error-control coding and matrix computations, whose underlying data flow graphs are based on finite projective-geometry(PG) based balanced bipartite graphs. Many of these applications are actively being researched upon. Almost all these applications need bipartite graphs of the order of tens of thousands in practice, whose nodes represent paral… ▽ More A number of computations exist, especially in area of error-control coding and matrix computations, whose underlying data flow graphs are based on finite projective-geometry(PG) based balanced bipartite graphs. Many of these applications are actively being researched upon. Almost all these applications need bipartite graphs of the order of tens of thousands in practice, whose nodes represent parallel computations. To reduce its implementation cost, reducing amount of system/hardware resources during design is an important engineering objective. In this context, we present a scheme to reduce resource utilization when performing computations derived from PG-based graphs. In a fully parallel design based on PG concepts, the number of processing units is equal to the number of vertices, each performing an atomic computation. To reduce the number of processing units used for implementation, we present an easy way of partitioning the vertex set. Each block of partition is then assigned to a processing unit. A processing unit performs the computations corresponding to the vertices in the block assigned to it in a sequential fashion, thus creating the effect of folding the overall computation. These blocks have certain symmetric properties that enable us to develop a conflict-free schedule. The scheme achieves the best possible throughput, in lack of any overhead of shuffling data across memories while scheduling another computation on the same processing unit. This paper reports two folding schemes, which are based on same lattice embedding approach, based on partitioning. We first provide a scheme for a projective space of dimension five, and the corresponding schedules. Both the folding schemes that we present have been verified by both simulation and hardware prototyping for different applications. We later generalize this scheme to arbitrary projective spaces. △ Less

Submitted 1 July, 2011; originally announced July 2011.

Comments: 31 pages, to be submitted to some discrete mathematics journal

MSC Class: 51E20

Journal ref: Discrete Mathematics, Algorithms and Applications Vol. 5, No. 4 (2013)