Table of Contents

High Peformance Computing Lab : http://www.ee.iitb.ac.in/~hpc

- Combinatorial optimization
- Matroid Theory
- Submodular Functions
- Linear/Integer programming
- Network Flows

- High Performance Computing
- FPGA-based accelerated computing
- GPU based acceleration
- High Performance Circuit Simulation

- Algorithms Design and Analysis
- Graph Theory
- Geometric Design and Graphics
- Software/Hardware Development Projects

- B. Tech in Computer Science and Engineering from IIT Bombay, 1986
- M. Tech in Computer Science from IIT Madras, 1987
- PhD in Computer Science from IIT Bombay, 1992
- Fellow of Alexander von Humboldt Foundation, at Research Inst. of Discrete Mathematics, Univ. Bonn, Germany, January 1993 - September 1994
- Assistant Professor of Mathematics, IIT Bombay, October 1994 - September 1998
- Associate Professor of Mathematics, IIT Bombay, October 1998 - 2006
- Associate Professor of Electrical Engineering, IIT Bombay, 2007 - 2011
- Professor of Electrical Engineering, IIT Bombay, 2011 - present

Department of Electrical Engineering

IIT Bombay, Powai

Mumbai 400 076, India

Email : patkar[AT]ee.iitb.ac.in

Phone (Internal(O)) : (0091 22) - 2576-7490

Phone (Internal(R)) : 8490

Office room no: 231-C

Fax: (0091 22) - 25723707

- Ravi Shankar Gautam (Geometric Design), Dept. Math
- B.R.S.M. Jothi (Optimization in VLSI CAD, Scheduling) , Dept Math
- Hrishikesh Sharma ( Finite Projective Geometry, FPGA based PG-LDPC )
- Yogesh Save ( as a co-supervisor ) ( Circuit Simulation )

- 70 postgraduate (MTech/MSc) thesis supervised

- Referee for “Discrete Mathematics”, “Discrete Applied Mathematics”, “Maths of OR”, “IEEE Trans. for VLSI CAD” etc.
- Referee for “Foundations of Software Technology and Theoretical Computer Science”, “VLSI Design” etc.

Journal Articles, HandBook Chapters and Patents are marked J Articles in Conferences and Proceedings are marked C

——————————————————————————–

Publications

C-[73] Vinay BY Kumar, Deval Shah, Mandar Datar and Sachin B Patkar, “Lightweight Forth Programmable NoCs” in 2018 31st International Conference on VLSI Design and 2018 17th International Conference on Embedded Systems (VLSID), 2018, pp 368-373

J-[72] H. Narayanan and Sachin B. Patkar, “Matroids”, in Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, Editor-in-Chief K. Thulasiraman, Chapman and Hall/CRC Press, 2016 . pp. 879-922

J-[71] Sachin B. Patkar and H. Narayanan, “Graph and Hypergraph Partitioning”, Invited Chapter in Handbook of Graph Theory and Algorithms, Editor-in-Chief K. Thulasiraman, Chapman and Hall/CRC Press, 2016, pp. 829-878

C-[70] Vinay BY Kumar, K Dhiman, M Datar, A Pacharne, H Narayanan and Sachin B Patkar, “Relaxation based circuit simulation acceleration over CPU-FPGA”, 29th International Conference on VLSI Design and 2016 15th International Conference on Embedded Systems (VLSID), 2016 , pp 409-414

C-[69] Vinay B. Y. Kumar, Pinalkumar Engineer, Mandar Datar, Yatish Turakhia, Saurabh Agarwal, Sanket Diwale and Sachin B. Patkar. “Framework for Application Mapping over Packet-Switched Network of FPGAs: Case Studies”, in: International Workshop on FPGAs for Software Programmers (FSP 2015), London, UK, September 1 – 4, 2015, arXiv preprint arXiv:1508.06823

C-[68] Dash S., Bangera V., Kumar V. B. Y., Patkar S. B., Trivedi G : “Power Grid Analysis on Parallel Computing Platforms”, MAREW, Microwave and Radio Electronics Week 2015 25th International Conference Radioelektronika 2015, 14th Conference on Microwave Techniques COMITE 2015, Pardubice, Czech Republic, April, 21 - 23, 2015

C-[67] Barath Sastha S, Sachin B Patkar and Y. S. Rao : Synthetic Aperture Radar Image Processing by Range Migration Algorithm using Multi-GPUs, GPU Technology Conference, GTC 2015, MARCH 17-20, 2015, SILICON VALLEY

C-[66] Pinalkumar J. Engineer, Ayan Mishra, Rajbabu Velmurugan, Sachin Patkar : GPU implementation of Particle Filter based Object Tracking, GPU Technology Conference, GTC 2015, MARCH 17-20, 2015, SILICON VALLEY

C-[65] P Engineer, R Velmurugan, S Patkar : Parameterizable FPGA Framework for Particle Filter Based Object Tracking in Video, VLSI Design (VLSID), 2015 28th International Conference on, 35-40, Banglore, 2015, pp. 35-40, 3-7 Jan. 2015

C-[64] VBY Kumar, S Maity, SB Patkar : Storage-allocation to sequential structures in High-Level Synthesis-assisted prototyping, Computer Design (ICCD), 2014 32nd IEEE International Conference on, 464-469, 19-22 Oct. 2014, Seoul, South Korea 2014

C-[63] V Kumar, VBY Kumar, SB Patkar : FPGA-based implementation of M4RM for matrix multiplication over GF (2), VLSI Design and Test, 18th International Symposium on, 1-2, Banglore, 2014

C-[62] J Porwal, S Diwale, VBY Kumar, SB Patkar : Projective Geometry and precedence constraint based application mapping on multicore network-on-chip systems, VLSI Design, Automation and Test (VLSI-DAT), 2014 (IEEE) International Symposium on , 28-30 April 2014, Hsinchu city, Taiwan

C-[61] H Sharma, S Sivasubramanian, S Patkar : Optimal communication scheduling for iterative decoding of irregular codes, Communications (NCC), 2014 Twentieth National Conference on, pp. 1-5, Feb. 28 2014-March 2 2014, Kanpur, India, 2014

C-[60] Jasveer Singh T Jethra, Sachin B Patkar, Shamik Datta: Remote Triggered FPGA based Automated System, 11th International Conference on Remote Engineering and Virtual Instrumentation (REV), 309 - 314, Porto, Portugal, 26-28 Feb. 2014

J-[59] S Choudhary, H Sharma, S Patkar: Optimal folding of data flow graphs based on finite projective geometry using vector space partitioning, Discrete Mathematics, Algorithms and Applications 5 (04), 2013

J-[58] Hrishikesh Sharma and Sachin B. Patkar: “A Design Methodology for Optimally Folded, Pipelined Architectures in VLSI Applications using Projective Space Lattices”, accepted for publication in Elsevier Journal of Microprocessors and Microsystems 37 (6), 674-683, 2013

J-[57] Yogesh Dilip Save, H. Narayanan, Sachin B. Patkar, “Solution of PDEs-Electrically Coupled Systems with Electrical Analogy.” Integration, the VLSI Journal 46 (4), 427-440, 2013

C-[56] Prateek Saxena, Vinay B.Y. Kumar, Dilawar Singh. H Narayanan and Sachin B. Patkar, “Hardware –Software Scalable Architectures for Gaussian Elimination over GF(2) and higher Galois Fields” to appear in Proceedings of PECCS 2013, Barcelona.

C-[55] Saurabh Agrawal, Debapratim Ghosh, Abhishek Kamath, Kaushlesh Sharma, Sneha Mistry, Madhumita Date, Sachin B. Patkar, and Dinesh Sharma: “An Affordable on-site and Remote Laboratory Solution for a Course in Modern Digital Design”, accepted for publication in IEEE EDUCON, Berlin 13th-17th March 2013.

C-[54] Yogesh Dilip Save, H.Narayanan, Sachin B. Patkar, “Memory Efficient Implementation of Two Graph based circuits Simulator for PDE-Electrical Analogy”, in proceedings of 26th International Conference on VLSI Design, Pune, India 2013

C-[53] Sumeet Agrawal, Pinalkumar Engineer, Rajbabu Velmurugan and Sachin B. Patkar, “FPGA Implementation of particle filter based object tracking in video”, 3rd International Symposium on Electronic System Design (ISED), Kolkata, 19th-22nd December 2012.

C-[52] Samir Shelke, Madhumita Date, Sachin B. Patkar, Rajbabu Velmurugan, and Preeti Rao, “A Remote Lab For Real-Time Digital Signal Processing”, EDERC2012: 5th European DSP Education and Research Conference, 13- 14 September 2012, Amsterdam, Netherlands

C-[51] Yogesh Dilip Save, H. Narayanan, Sachin B. Patkar, “Two Graph based cicuitsimulator for PDE –Electrical Analogy”, 25thIntl. in proceedings of International Conference on VLSI Design, 2012

C-[50] Madhumita Date, Sachin B. Patkar, Mahesh Patil, Narendra N., Samir Shelke, Abhishek Kamath, and DebapratimGhosh, “e-prayog: A New Paradigm for Electronics Laboratories”, IEEE International Conference on Technology Enhanced Education (ICTEE 2012), 2012

J-[49] Yogesh Dilip Save, H. Narayanan and Sachin B. Patkar, “Solution of Partial Differential Equations by electrical analogy”, (Elsevier) Journal of Computational Science 2 (2011) 18–30

C-[48] Subhasis Das and Sachin Patkar, “A Compact Gaussian Random Number Generator for Small Word Lengths”, Applied Reconfigurable Computing - 2011 (ARC-2011), Belfast, Ireland, 23-25 March 2011

C-[47] Sumedh Attarde, Siddharth Joshi, Yash Deshpande, Sunil Puranik and Sachin Patkar, “Double Precision Sparse Matrix Vector Multiplication Accelerator on FPGA”, PECCS-2010 (Pervasive and Embedded Computing and Communications Systems - 2011)

C-[46] Balwinder Kumar, Yogesh Dilip Save, H. Narayanan, and Sachin B. Patkar, “A Simple Relaxation based Circuit Simulator for VLSI Circuits with Emerging Devices”, CSC, 2011 (The 2011 International Conference on Scientific Computing), USA, 2011

C-[45] Hrishikesh Sharma, Subhasis Das, Rewati Raman Raut and Sachin Patkar, “HIGH THROUGHPUT MEMORY-EFFICIENT VLSI DESIGNS FOR STRUCTURED LDPC DECODING”, PECCS-2010 (Pervasive and Embedded Computing and Communications Systems - 2011)

J-[44] B. Adiga, S. Chowdhary, H. Sharma, and S. Patkar, System for Error Control Coding using Expander-like codes constructed from higher dimensional Projective Spaces, and their Applications, Indian Patent Requested (2010), 2455/MUM/2010, (78 pages)

C-[43] Swadesh Choudhary, Tejas Hiremani, Hrishikesh Sharma and Sachin Patkar, “A Folding Strategy for DFGs derived from Projective Geometry based graphs”, The 2010 International Congress on Computer Applications and Computational Science (CACS 2010), Singapore, Dec 4-6, 2010

C-[42] Subhendu Roy, Yogesh Dilip Save, H. Narayanan and Sachin B. Patkar, “Large Scale VLSI Circuit Simulation Using Point Relaxation”, CSC, 2010 (The 2010 International Conference on Scientific Computing), July 12-15, USA, 2010

J-[41] V.B.Y. Kumar, S. Joshi, Sachin B. Patkar, and H. Narayanan, “FPGA-based High Performance Double-Precision Matrix Multiplication”, International Journal of Parallel Programming, Springer, vol 38, issue 3, 2010, pp. 322-338 (online DOI: 10.1007/s10766-010-0131-8) (17 pages)

C-[40] A. Maringanti, V. Athavale, and S. Patkar, “Acceleration of the conjugate gradient method for circuit simulation using CUDA,” in Proc. 16th International Conference on High Performance Computing, 2009.

C-[39] D. Baviskar and S. Patkar, “A Pipelined Simulation Approach for Logic Emulation Systems,” in Proc. IEEE International Symposium on Circuits and Systems, 2009, pp. 1141-1144.

C-[38] V.B.Y Kumar, S. Joshi, S. Patkar and H. Narayanan, “FPGA-based High Performance Double- Precision Matrix Multiplication,” in Proc. 22nd Int. Conference on VLSI Design, 2009, pp. 341-346.

C-[37] V.S. Sankar, S. Patkar, and H. Narayanan, “Exploiting Hybrid Analysis in Solving Electrical Networks,” in Proc. 22nd International Conference on VLSI Design, 2009, pp. 206-211.

C-[36] J. Porwal, S. B. Patkar, and C. Poojari, “Approximate Solutions for Deterministic and Stochastic Multi-Dimensional Sequencing,” Optimization Online 2007, http://www.optimization-online.org/DB_FILE/2007/07/1722.pdf

J-[35] Madhav P. Desai, Himanshu Sharma, Mitra Purandare and Sachin B. Patkar, “A system and method for emulating a logic circuit design using programmable logic devices”, Patent Application No. 211/MUM/2005, Published 2005-06-04, Filed 2005-02-05, United States Patent Application Pub. No. US 2006/0247909 A1 , Pub. Date Nov. 2, 2006

C-[34] S. B. Patkar, C. Poojari, B..S.M. Jothi : “A Web-Enabled Partitioning Based Linear Programming Optimization System”, Applied Mathematical Programming and Modeling, APMOD 2006, Madrid, Spain, 19-21 June 2006

J-[33] B.R.S.M Jothi and S. Patkar, “Distributed decision support system and various algorithms for scheduling in heat treatment plant for bearings,” WSEAS Transactions on Systems, vol. 4, no. 6, pp. 854-863, 2005.

C-[32] J. Porwal and S. B. Patkar, “Algorithms for scheduling of data transfer across FPGAs in a grid,” in Proc. International Conference on Engineering of Reconfigurable Systems and Algorithms, 2005.

J-[31] A. Deshpande, S B. Patkar, H. Narayanan: Submodular Theory Based Approaches for Hypergraph Bipartitioning, wseas trans. On Circuits And Systems 2005, Vol 4; Issue 6, pp. 647-655.

J-[30] S. B. Patkar, Himanshu Sharma and H. Narayanan: Efficient Network Flow based Ratio-cut Netlist Hypergraph Partitioning, wseas transactions on Circuits and Systems, vol. 3, no. 1, January 2004, pp. 47-53.

C-[29] S. B. Patkar, BRSM Jothi : Multidimensional Job Scheduling, Applied Mathematical Programming and Modeling, APMOD 2004, London, UK, June 2004

J-[28] R. S. Gautam and S. Patkar, “Fitting convex surface to scatter data points with applications to medical imaging,” WSEAS Transactions on Computers, vol. 3, no. 1, pp. 50-56, 2004.

J-[27] S. Patkar and H. Narayanan, “Fast on-line/off-line algorithms for optimal reinforcement orcement of a network and its connections with principal partition,” Journal of Combinatorial Optimization, vol. 7, no. 1, pp. 45-68, 2003.

J-[26] S. Patkar and H. Narayanan, “Improving graph partitions using submodular functions,” Discrete Applied Mathematics (Special Issue on Submodularity), vol. 131, pp. 535-553, 2003.

J-[25] M. P. Desai, H. Narayanan, and S. Patkar, “The realization of finite state machines by decomposition and the principal lattice of partitions of a submodular function,” Discrete Applied Mathematics (Special Issue on Submodularity), vol. 131, pp. 299-310, 2003.

C-[24] S. B. Patkar and H. Narayanan, “An Efficient Practical Heuristic for good ratio-cut partitioning,” in Proceedings of International Conference on VLSI Design, 2003.

C-[23] S.B. Patkar, B.R.S.M. Jothi and Amey Pathak, New Partitional Approaches for Identifying Natural Clusters in Large Datasets, in proceedings of International Conference and Instructioal Workshop in Industrial Mathematics (ICIWIM 2002), 2002, pp. 307-326.

C-[22] S. B. Patkar, R.S. Gautam, V. Goel, and P. Srivastav, “BezierPkg: An Interactive Tool for Generation of Smooth Surfaces,” in Proceeding of WSEAS International Conference on Information and Automation, 2002.

C-[21] S. B. Patkar, V. Kumar, H. Kaur, and B. Hore, “A Graph Partitioning System for Natural Unbalanced Partitions,” in Proceeding of WSEAS International Conference on Information and Automation, 2002.

J-[20] S. Patkar and H. Narayanan, “A note on optimal covering augmentation for graphic polymatroids,” Information Processing Letters, vol. 79, pp. 285-290, 2001.

J-[19] S. Fujishige and S. Patkar, “Realization of set functions as cut functions on graphs and hypergraphs,” Discrete Mathematics, vol. 226, pp. 199-210, 2001.

J-[18] S. Skaria, S. Patkar, and S.S.S.P Rao, “Performance enhancement using register windows on UltraSPARC,” The Journal of the Computer Society of India, vol. 30, no. 1, pp. 34-43, 2000.

C-[17] S. B. Patkar and H. Narayanan, “Fast On-line/off-line algorithms for optimal reinforcement of a network and its connections with principal partition,” in Proceedings of Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST TCS-20), Lecture Notes in Computer Science - 1974, Springer, 2000, pp. 94-105.

C-[16] S. B. Patkar and H. Narayanan.: Applications of Submodular Functions to VLSI CAD, presented at ISMP2000: International Symposium on Mathematical Programming, Atlanta, USA, August 7-11, 2000.

C-[15] C.R. Venugopal, S.S.S.P. Rao, and S. B. Patkar, “Priority Scheduling in Parallel I/O Systems,” in Proc. International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’99), 1999.

C-[14] C.R. Venugopal, S.S.S.P. Rao, and S. B. Patkar, “Parallel I/O: Modeling and Scheduling Policies,” in Proceedings of TENCON’99, 1999.

C-[13] P. Gowaikar, M. Sohoni, S. Patkar, and M. Chandramouli, “Development of a multi-FPGA Netlist Partitioner and general purpose graph partitioner,” in PhotoMask’98, 1998.

C-[12] S. B. Patkar, S. Batterywala, M. Chandramouli, and H. Narayanan, “A New Partitioning Strategy Based on Supermodular Functions,” in Proc. 10th Int. Conference on VLSI Design, 1997.

J-[11] H. Narayanan, S. Roy, and S. Patkar, “Approximate algorithms for min-k-overlap problems using the principal lattice of partitions approach,” Jl. of Algorithms, vol. 21, pp. 306-330, 1996.

J-[10] S. Fujishige and S. Patkar, “The orthant non-interaction theorem for certain combinatorialpolyhedra and its implications in the intersection and the dilworth truncation of bisubmodular functions,” Optimization, vol. 34, pp. 329-339, 1995.

J-[9] S. Patkar, B. Servatius, and K.V. Subrahmanyam, “Abstract and generic rigidity in the plane,” Journal of Combinatorial Theory, vol. 62, no. 1, 1994.

C-[8] H. Narayanan, S. Roy, and S. B. Patkar, “Approximate algorithms for Min-k-overlap problems using the principal lattice of partitions approach,” in Proceedings of International Conference of Mathematical Foundations of Computer Science, 1994.

C-[7] S. B. Patkar, K.V. Subrahmanyam and H. Narayanan.: On the membership problem over Polymatroid intersection, Technical Report, Dept. of Comp. Sc. and Engg., IIT Bombay, 1992, also presented at ECCO VII: European Conference on Combinatorial Optimization, February 21-22, 1994, Milan, Italy.

C-[6] S. Fujishige, and S.B. Patkar.: Convolution and Dilworth Truncation for Bisubmodular Polyhedra, Conference Discrete Optimization, June 1994, Weimar, Germany.

C-[5] S. B. Patkar and H. Narayanan, “Principal lattice of partitions of submodular functions ongraphs: Fast algorithms for principal partition and generic rigidity,” in Proceedings of the annual International Symposium on Algorithms and Computation (ISAAC), 1992, pp. 41-50.

C-[4] Narayanan, H., Roy, S. and Patkar, S.: Min k-cut and the Principal Partition of a graph, in Proc. of second National Seminar on Theoretical Computer Science, India, 1992.

C-[3] S. B. Patkar and H. Narayanan, “Fast algorithm for the principal partition of a graph,” in Proceedings of annual Symposium on Foundations of Software Technology and Theoretical Computer Science (FST TCS-11), Lecture Notes in Computer Science - 560, Springer, 1991.

C-[2] S. B. Patkar and C. Pandurangan, “Extension of PASCAL for SIMD processing,” in Proceedings of TENCON, 1989.

C-[1] S. B. Patkar and C. Pandurangan, “Optimal parallel algorithms for matrix transposition and the simulation of perfect shuffle network on the mesh,” in Proc. International Conference on Parallel Processing and its Applications, 1987.

Submitted (or ready manuscipt) Papers

Abhishek Patil , Hrishikesh Sharma , Shreeniwas Sapre , B.S. Adiga and Sachin Patkar, “Projective Geometry based Fast, Conflict-free Parallel Matrix Computations”, to be submitted The International Journal of Parallel, Emergent and Distributed Systems,

Gaurav Trivedi, Yogesh Dilip Save, S. B. Patkar and H. Narayanan, “Application of the fast nonlinear DC Analyzer to Min Cost Flow and Single Source Shortest Path Problems”, to be submmited for publication

(Spring 2012) EE-224 Digital Systems

(associate instructor for) EE-668 System Design

http://www.ee.iitb.ac.in/~eeoffice/curriculum/ee_pgcourses_syl.htm#EE668 Text that I will adopt is : CMOS VLSI Design , Weste and Harris, Addison-Wesley, 4edition http://www3.hmc.edu/~harris/cmosvlsi/4e/index.html

(Autumn 2011)

EE-677 Foundations of VLSI CAD

Textbook : "Logic Synnthesis and Verification Algorithms", Hachtel and Somenzi, Springer

course moodle URL : http://moodle.iitb.ac.in/course/view.php?id=2333

EE-453 Advanced Computing

course moodle URL http://moodle.iitb.ac.in/course/view.php?id=2309

Foundations of VLSI CAD, EE

Advanced Computing for Electrical Engineers, EE

Digital Systems, EE,

Computer Systems, EE,

Lab and Computational Techniques, EE,

Microprocessors Lab, EE,

Digital Circuits Lab, EE,

Combinatorial Optimization, MSc Maths,

Discrete Algorithms, MSc Maths,

Algorithms and Complexity, MSc Maths,

Data Structures, MSc Maths,

Applied Linear Algebra, MSc Maths, Math.

Mathematical Elements for Comp. Graphics, MSc Maths,

Computer Aided Geometric Design, MSc Maths,

Numerical Computation, UG (CSE, MSc Math),

Mathematics I (Course Associate),

Mathematics II (Course Associate)

System Programming, MSc Maths,

Programming Languages Lab, MSc Maths,

Software Systems Lab, B.Tech (CSE) and MSc Maths

Unix and C Lab, MSc Maths,

Informatics Lab, MSc Maths,