Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Manitoba

$22,000.00

Hardware Accelerated Bio-Inspired Parallel Algorithms for Real World Applications

EF 2016-17

Résumé
Consider an example such as Facebook where you may be connected to many friends. Let's represent a friend as a ""node"" (circle) and the connection between friends as a link (straight line). Imagine having billions of nodes and links. This representation is called a graph or network. There are many real world problems in sociology, neuroscience, medicine, etc., that be can be represented as graphs. There are many issues related to these graphs. For example, on Facebook we may want to cluster groups of people who share similar interests. Then the graph can be decomposed into clusters such that objects within a cluster have high similarity while objects between clusters have low similarity. This is called the clustering problem. Can we cluster a graph with billions of nodes and links? It is impossible to do this visually. My research focuses on solving such problems by borrowing ideas from nature. For example, ants clean up their nest (brood) by systematically collecting dead ants and piling them depending on their size and shape (called ant brooding). My research proposes solution to the clustering problem using ant brooding technique. This is quite challenging because we need to mathematically model the problem and create algorithms (step-by-step procedures) using ant brooding to solve the problem. Due to the large graph size, providing a solution fast on a single computer is difficult. Parallel computing involves using many computers to solve a given problem fast cooperatively. Today's general-purpose computers (PC) come with not one CPU (central processing unit or processor) but with 2, 4 or 8 identical processors called cores, allowing simultaneous execution of many tasks. These days, graphical processing units (GPUs) or accelerators have become mainstream (e.g., used for games, video) with hundreds of processors providing lots of potential parallelism. The GPUs come as a single chip and can be installed on any PC. We can fuse CPU and accelerator together on a single chip, like in AMD Accelerated Processing Unit (APU), providing massive amount of parallelism. These are called many-core machines. There is a lot of parallelism within an ant colony. Each ant works independently (very parallel) and can self-organize quite fast. They communicate with each other indirectly (stigmergic communication), at the same time working cooperatively to solve a problem. Indirect communication allows for minimal global synchronization, an asset on parallel computers. Less synchronization means processors are busy doing computations increasing performance. I propose to use many-core machines to find an answer to the clustering problem fast. Therefore, the focus of this proposed research is on the design, development and performance evaluation of nature-inspired techniques to solve large real world problems on parallel computers. In this cycle of my Discovery Grant, I expect to train 3 Undergrad., 4 MSc and 7 PhD students.
Programme
Discovery Grants Program - Individual
Emplacement
Manitoba, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2016-06052
Name nom
Thulasiraman, Parimala
Department département
Computer Science - 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
2016
Competition year année de concours
2016
Award amount
22000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
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
2704
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Distributed and parallel processing
Research subject fr
Traitement réparti et simultané
Partie
1
Nb partie
1
Application title
Hardware Accelerated Bio-Inspired Parallel Algorithms for Real World Applications
Keyword
NSERC
Application summary
Consider an example such as Facebook where you may be connected to many friends. Let's represent a friend as a ""node"" (circle) and the connection between friends as a link (straight line). Imagine having billions of nodes and links. This representation is called a graph or network. There are many real world problems in sociology, neuroscience, medicine, etc., that be can be represented as graphs. There are many issues related to these graphs. For example, on Facebook we may want to cluster groups of people who share similar interests. Then the graph can be decomposed into clusters such that objects within a cluster have high similarity while objects between clusters have low similarity. This is called the clustering problem. Can we cluster a graph with billions of nodes and links? It is impossible to do this visually. My research focuses on solving such problems by borrowing ideas from nature. For example, ants clean up their nest (brood) by systematically collecting dead ants and piling them depending on their size and shape (called ant brooding). My research proposes solution to the clustering problem using ant brooding technique. This is quite challenging because we need to mathematically model the problem and create algorithms (step-by-step procedures) using ant brooding to solve the problem. Due to the large graph size, providing a solution fast on a single computer is difficult. Parallel computing involves using many computers to solve a given problem fast cooperatively. Today's general-purpose computers (PC) come with not one CPU (central processing unit or processor) but with 2, 4 or 8 identical processors called cores, allowing simultaneous execution of many tasks. These days, graphical processing units (GPUs) or accelerators have become mainstream (e.g., used for games, video) with hundreds of processors providing lots of potential parallelism. The GPUs come as a single chip and can be installed on any PC. We can fuse CPU and accelerator together on a single chip, like in AMD Accelerated Processing Unit (APU), providing massive amount of parallelism. These are called many-core machines. There is a lot of parallelism within an ant colony. Each ant works independently (very parallel) and can self-organize quite fast. They communicate with each other indirectly (stigmergic communication), at the same time working cooperatively to solve a problem. Indirect communication allows for minimal global synchronization, an asset on parallel computers. Less synchronization means processors are busy doing computations increasing performance. I propose to use many-core machines to find an answer to the clustering problem fast. Therefore, the focus of this proposed research is on the design, development and performance evaluation of nature-inspired techniques to solve large real world problems on parallel computers. In this cycle of my Discovery Grant, I expect to train 3 Undergrad., 4 MSc and 7 PhD students.