Hardware Accelerated Bio-Inspired Parallel Algorithms for Real World Applications

适用于现实世界应用的硬件加速仿生并行算法

• 批准号: RGPIN-2016-06052
• 负责人: Thulasiraman, Parimala
• 金额: $ 1.6万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=616074
• 关键词: Hardware; Accelerated; Bio; Inspired; Parallel

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.

考虑一个例如Facebook之类的示例，您可能会与许多朋友联系。让我们代表一个朋友为“节点”（圈子），而朋友之间的连接则为链接（直线）。想象一下有数十亿个节点和链接。此表示称为图形或网络。社会学，神经科学，医学等中存在许多现实世界中的问题，可以表示为图。与这些图相关的问题很多。例如，在Facebook上，我们可能希望将具有相似兴趣的人组成。然后将图分解为群集，使群集中的对象具有很高的相似性，而簇之间的对象相似性较低。这称为聚类问题。我们可以将图形与数十亿个节点和链接共同集合吗？不可能在视觉上执行此操作。我的研究重点是通过借鉴自然的想法来解决此类问题。例如，蚂蚁通过系统地收集死蚂蚁并根据其大小和形状（称为蚂蚁育雏）来清理巢（育雏）。我的研究建议解决了使用蚂蚁育育技术解决聚类问题的解决方案。这是非常挑战的，因为我们需要使用蚂蚁育成解决问题来数学上对问题进行建模并创建算法（分步过程）。 由于图形尺寸较大，因此很难在一台计算机上快速提供解决方案。并行计算涉及使用许多计算机快速解决给定问题。当今的通用计算机（PC）没有一个CPU（中央处理单元或处理器），而是2、4或8个相同的处理器称为内核，从而可以简单地执行许多任务。如今，图形处理单元（GPU）或加速器已成为主流（例如，用于游戏，视频），数百个处理器提供了许多潜在的并行性。 GPU作为单个芯片出现，可以安装在任何PC上。我们可以将CPU和加速器融合在一起，例如在AMD加速器（APU）中，提供大量的并行性。这些称为多核机。 蚂蚁殖民地中有很多并行性。每个蚂蚁独立工作（非常平行），并且可以很快地自组织。他们间接地互相交流（柱头沟通），同时协同工作以解决问题。间接通信允许最小的全局同步，这是平行计算机上的资产。较少的同步意味着处理器正在忙于进行计算，以提高性能。我建议使用多核机快速找到群集问题的答案。 因此，这项拟议的研究的重点是对自然风格技术的设计，开发和性能评估，以解决并行计算机上的大型现实世界问题。在我的发现赠款的这一周期中，我希望培训3个本科生，4个MSC和7名博士生。