Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Manitoba

$15,000.00

Lock-free data structures

FY 2007-08

Summary
The results of this research will help programmers write code that allows many machines to work on the same data at the same time yet not interfere with each other.Sometimes the amount of data can be very large and sometimes the correct piece of data may be urgently needed.  To help searchers find what they want in the data quickly, programmers have designed clever structures for storing data that allow the searcher to do something faster than ``search through all the data until you find what you want''.  Associated with these data structures are methods of keeping the data up to date (inserting new items and deleting old items) that maintain the clever search structure.Programming becomes much more complicated if new data can be inserted at the same time as old data is being deleted at the same time as searches are under way.  Unless great care is taken, the data structure can become corrupted and searches may return incorrect results.  At the same time, programmers want as many searches and updates to happen simultaneously as can be allowed without causing havoc.  Thus, simplistic schemes that lock all but one updater out of the data structure at a time can cause problems.  Lock-free schemes that allow as many concurrent updates and searches as possible are preferred.The aim of this research is to take complex data structures and use lock-free schemes to allow concurrent updates and searches.  The research benefits Canada by providing tools (concurrent data structures) to make the complex task of concurrent  programming easier.  As parallel shared-memory machines become more prevalent, the impact of this work will increase.
Program
Discovery Grants Program - Individual
Location
Manitoba, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
155240-2007
Name nom
Cameron, Helen
Department département
Computer Science
Organization id
19
Institution établissement
University of Manitoba
Province en
Manitoba
Province fr
Manitoba
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2007
Competition year année de concours
2007
Award amount
15000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
330
Committee name en
Computing and Information Sciences - A
Committee name fr
Informatique - A
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
3
Application title
Lock-free data structures
Keyword
NA
Application summary
The results of this research will help programmers write code that allows many machines to work on the same data at the same time yet not interfere with each other.Sometimes the amount of data can be very large and sometimes the correct piece of data may be urgently needed.  To help searchers find what they want in the data quickly, programmers have designed clever structures for storing data that allow the searcher to do something faster than ``search through all the data until you find what you want''.  Associated with these data structures are methods of keeping the data up to date (inserting new items and deleting old items) that maintain the clever search structure.Programming becomes much more complicated if new data can be inserted at the same time as old data is being deleted at the same time as searches are under way.  Unless great care is taken, the data structure can become corrupted and searches may return incorrect results.  At the same time, programmers want as many searches and updates to happen simultaneously as can be allowed without causing havoc.  Thus, simplistic schemes that lock all but one updater out of the data structure at a time can cause problems.  Lock-free schemes that allow as many concurrent updates and searches as possible are preferred.The aim of this research is to take complex data structures and use lock-free schemes to allow concurrent updates and searches.  The research benefits Canada by providing tools (concurrent data structures) to make the complex task of concurrent  programming easier.  As parallel shared-memory machines become more prevalent, the impact of this work will increase.
University of Manitoba - $15,000 Grant (2007-08) | Canada Spends