An Efficient Software Framework for developing Reliable Multi-threaded Applications for Multi-Core Architectures
Primary Information
Domain
Information & Communication Technology
Project No.
6918
Sanction and Project Initiation
Sanction No: F.No. 3-18/2015-TS.(Vol. III)
Sanction Date: 14/12/2016
Project Initiation date: 19/08/2017
Project Duration: 36
Partner Ministry/Agency/Industry
MEITY
Role of partner:Provide suitable applications and use-cases to deploy the STM libraries to developed as a part of this project. As a part of this project, we plan to develop a few use-cases: (1) Concurrent execution of smart cotnracts in Blockchain systems (2) MSTs, (3) Graph Coloring, (4) Automatic Video Surveillance. We expect that the partner ministry will find these applications useful and provide other suitable applications.
Support from partner:None so far. We hope that they provide support in future. To address this difficulty, we have identified a start-ups who in Hyderabad who will support with this project.
Principal Investigator
Sathya Peri
Indian Institute of Technology Hyderabad
Host Institute
Co-PIs
R.K. Shyamasundar
Indian Institute of Technology Bombay
C. Krishna Mohan
Indian Institute of Technology Hyderabad
Scope and Objectives
Objectives: The objective of this project is to develop an efficient software framework for multi-core systems which will manage all the shared memory and rid the programmer the burden of concurrency control. It is based on the idea of Software Transactional Memory Systems. We propose to build a STM system that is based on conflict-graph verification for conflict-serializability class used in databases. In addition to these desirable features, the proposed middle-ware will not have any undesirable side-effects. As a result, the developed software will be reliable as well as efficient. Scope: Traditionally locks have been used to synchronizing threads. Threads wishing to the access multiple shared data-items atomically, obtain locks for all the shared data-items, performs theaccess and then releases the locks. This approach is called as two phase locking (2PL). Lock-based parallel programming, however, is widely acknowledged as a difficult and error-prone task. Several classes of bugs that can result from mistakes in this area cannot be found by static analysis, and can sometimes be difficult to find even with the most rigorous testing, as they are only triggered under precise timing conditions while executing tasks in parallel. All of this increases the cost of developing high performance parallel software. More importantly, systems built using locks are difficult to compose without knowing about their internals. Correct fragments may fail when combined. Composition of software is a very useful property which is used to build large software systems using simpler software systems. Using composition existing pieces of correctly executing software can be trivially combined to form a larger piece of software that executes correctly. It is the basis of modular programming. Synchronization issues are with parallel programming can be quite challenging.
Deliverables
End of First Year: A study and report showing the current state of art in the field of database and memory transactions End of Second Year: A detailed technical report describing the theoretical framework of STMs designed to work on multi-core systems. The theoretical framework will be generic and not specific to any particular technology or programming language. End of Third Year: 1. Develop an efficient STM library for multi-core systems using the understanding gained as mentioned in the objective. In addition to being efficient, the STM library will also be (i) correct and (ii) not have any undesirable side-effects (iii) Has notion of progress in it. The performance of the STM system will be thoroughly tested w.r.t the applications which are of importance to the society (a) Improving the performance of Blockchain nodes. Specifically the nodes that creates blocks and validate them. We plan to use STMs to achieve this (b) Efficient algorithms for coloring of graphs. 2. Publish the results in peer-reviewed conferences and journals.
Scientific Output
1. Develop an efficient STM library for multi-core systems. In addition to being efficient, the STM library will also be (i) correct and (ii) not have any undesirable side-effects (iii) Has notion of progress in it. The performance of the STM system will be thoroughly tested w.r.t w.r.t the applications which are of importance to the society (a) Improving the performance of Blockchain nodes. Specifically the nodes that creates blocks and validate them. We plan to use STMs to achieve this (b) Efficient algorithms for coloring of graphs 2. Publish the results in peer-reviewed conferences and journals.
Results and outcome till date
A detailed technical report describing the theoretical framework of STMs designed to work on multi-core systems. The theoretical framework will be generic and not specific to any particular technology or programming language.
Societal benefit and impact anticipated
Over the last few decades, much of the gain in software performance can be attributed to increases in CPU clock frequencies. However around 2004, 50 years of exponential improvement in the performance of sequential computers ended. Industry's response to these changes was to introduce single-chip, parallel computers, variously known as "chip multiprocessors," "multicore," or "manycore" computers. In order to get a continued speedup on these processors, applications need to be able to harness the parallelism of the underlying hardware. This is commonly achieved using multi-threading. Therefore, there is an increasing need for programmers to produce applications in which multiple processes execute in parallel and coordinate to achieve some shared task. Due to these difficulties with locks, alternative approaches were looked into. Software transactional memory (STM) is an approach which has garnered significant interest as an elegant alternative for developing parallel programs. Software transactions are units of execution in memory which enable concurrent threads to execute seamlessly. Software transactions address many of the shortcomings of lock based systems. This idea originated from transactions in databases. Also, it was recently observed that STMs can benefit Blockchains. Blockchain is an encrypted, distributed ledger (or database) shared across multiple computers or nodes that are part of a community or system. Each node holds the identical copy of the ledger which is usually represented as a chain of blocks. Each block in the chain being a logical sequence of business (or financial) transactions. Several businesses have also adopted this innovative technology and have already achieved significant benefits some of which include greater transparency, enhanced security, improved traceability, increased efficiency and speed of transactions as a result reduced costs. Blockchains have become so popular that several State Governments (such as Telangana State Govt.) are using this for maintaining land & medical records. Thus with this project, we plan to develop tools that can improve various aspects of programming which can in turn benefit the society.
Next steps
Develop an efficient STM library for multi-core systems using the understanding gained as mentioned in the objective. In addition to being efficient, the STM library will also be (i) correct and (ii) not have any undesirable side-effects (iii) Has notion of progress in it. The performance of the STM system will be thoroughly tested w.r.t the applications which are of importance to the society (a) Improving the performance of Blockchain nodes. Specifically the nodes that creates blocks and validate them. We plan to use STMs to achieve this (b) Efficient algorithms for coloring of graphs.
Publications and reports
1. "A Simple and Practical Concurrent Non-blocking Unbounded Graph with Reachability Queries", Bapi Chatterjee, Sathya Peri, Muktikanta Sa, Nandini Singhal in the 20th International Conference on Distributed Computing and Networking (ICDCN), Bangalore, India, January 2019.
2. "An Innovative Approach to Achieve Compositionality Efficiently using Multi-Version Object Based Transactional Systems", Chirag Juyal, Sandeep Kulkarni, Sweta Kumari, Sathya Peri and Archit Somani in 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018) Tokyo, Japan, Nov 4 - Nov 7, 2018. Won the Best Student Paper Award at this conference.
3. "Efficient means of Achieving Composability using Object based Semantics in Transactional Memory Systems", Sathya Peri, Ajay Singh, and Archit Somani in The 6th International Conference on Networked Systems (NETYS) May 2018 at ESSAOUIRA, MOROCCO
4. "STMs in Practice: Partial Rollback vs Pure Abort Mechanisms", Anshu S. Anand, R. K. Shyamasundar, Sathya Peri. Concurrency and Computation: Practice and Experience, 2018. https://doi.org/10.1002/cpe.4465.
Patents
NA
Scholars and Project Staff
1. Mr. Archit Kumar Somani on the area of Object-based STM Sytems.
2. Ms. Sweta Kumari on exploring progress conditions in STM Sytems.
3. Mr. Parwat Singh Anjana working on parallel numeric and graph algorithms.
4. Mr. Chirag Juyal working on progress guarantees in Transactional Memory Systems.
5. Mr. Sachin Rathor working on efficient Traffic Data Analysis.
6. Mr. Anshu A Anand working on MSTs & Blockchains.
Challenges faced
We are currently facing two main difficulties: 1. Halfway through the project, we have been asked to revise our project deliverables. Earlier, our proposal was accepted with one set of deliverables & objectives. In the month of August 2018, we had a review meeting. There we have been asked to revise our objectives so that it can be useful to the industry. As a result our objective and plan had to be changed. 2. The partner industry has not given us any money till now. We have received only 50% of the project money for the 1st and 2nd years far. So, it is not clear how to proceed with the project and meet the deliverables without receiving the rest of the money.
Other information
We are in the process of finding another partner industry since we have not received any support from MEITY so far for this project. We are in touch with a start-ups in Hyderabad who are working on blockchains. They have given us a little financial support from them. We are looking to receive more from them.
Financial Information
-
Total sanction: Rs. 6000000
-
Amount received: Rs. 2205500
-
Amount utilised for Equipment: Rs. 1000000
-
Amount utilised for Manpower: Rs. 1476000
-
Amount utilised for Consumables: Rs. 37260
-
Amount utilised for Contingency: Rs. 36280
-
Amount utilised for Travel: Rs. 87006
-
Amount utilised for Other Expenses: 49792
-
Amount utilised for Overheads: Rs. 735000
Equipment and facilities
In the process of purchasing a few servers