Hardware Accelerated Bio-Inspired Parallel Algorithms for Real World Applications

举个例子，比如Facebook，你可能会和很多朋友联系在一起。让我们将朋友表示为“节点”(圈)，并将朋友之间的连接表示为链接(直线)。想象一下，有数十亿个节点和链接。这种表示称为图或网络。在社会学、神经科学、医学等领域，有许多现实世界的问题可以用图表来表示。与这些图表相关的问题有很多。例如，在Facebook上，我们可能希望将兴趣相似的人聚集在一起。然后，可以将该图分解成簇，使得簇内的对象具有高相似度，而簇之间的对象具有低相似度。这就是所谓的集群问题。我们能把一个有数十亿个节点和链接的图聚集在一起吗？这不可能在视觉上做到这一点。我的研究重点是通过借鉴自然的想法来解决这些问题。例如，蚂蚁通过系统地收集死蚂蚁并根据它们的大小和形状将它们堆放在一起(称为蚂蚁孵化)来清理它们的巢(窝)。本研究提出了基于蚂蚁孵化技术的聚类问题解决方案。这是非常具有挑战性的，因为我们需要对问题进行数学建模，并使用蚂蚁孵化来创建算法(逐步过程)来解决问题。 由于图的大小，在单台计算机上快速提供解决方案是困难的。并行计算涉及到使用多台计算机快速协作地解决给定问题。今天的通用计算机(PC)配备的不是一个CPU(中央处理单元或处理器)，而是2个、4个或8个相同的处理器，称为核心，允许同时执行许多任务。如今，图形处理单元(GPU)或加速器已成为主流(例如，用于游戏、视频)，数百个处理器提供了大量潜在的并行性。这些图形处理器以单芯片的形式出现，可以安装在任何PC上。我们可以将CPU和加速器融合在一块芯片上，就像在AMD加速处理单元(APU)中一样，提供大量的并行性。这些机器被称为多核机器。 在一个蚂蚁群体中，存在着大量的并行性。每只蚂蚁都独立工作(非常并行)，并且能够非常快速地自组织。他们相互间接地交流(羞辱的交流)，同时合作解决问题。间接通信允许最小程度的全局同步，这是并行计算机上的一项资产。较少的同步性意味着处理器忙于进行提高性能的计算。我建议使用多核机器来快速找到集群问题的答案。 因此，这项研究的重点是在并行计算机上设计、开发和评估受自然启发的技术来解决大型现实世界的问题。在我的探索助学金周期中，我预计将培养3名本科生、4名硕士和7名博士生。

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.