Computer Architecture Support for Complex Networks

点击翻译按钮获取中文摘要

Complex networks play an important role in our lives today. They can be used to gain a better understanding of our actions in the past, predict our actions in the future, and use these predictions to influence outcomes.  For example, product recommendation systems represent a user's interactions with their database of items and past purchase histories to suggest future items that may be of interest to the user.  The potential benefits of using complex networks for inferences are enormous.  They are already in use for the following applications: traffic congestion, infectious disease and security threat analyses. A key challenge in inferring properties from complex networks involves performing queries on complex networks efficiently.  This is difficult because of the expected growth in size of future complex networks ranging from hundreds to thousands of petabytes.  This brings about an interesting observation that future computing platforms used to query complex networks will be accessing large amounts of data instead of performing large amounts of computation.  This means that complex network workloads will not be dominated by computation, but accesses to data.  Unfortunately, modern computing platforms are not designed based on this observation, which would result in large query times on complex networks. Consequently, the long-term vision of the research program is to investigate the design of computing platforms for fast and efficient querying of large complex networks. Dr. Patel proposes to address three topics in this proposal. The first topic investigates notions of data locality that best represent proximity in complex networks, termed graph-locality.  Dr. Patel believes that queries on complex networks do not exhibit traditional notions of spatial and temporal locality. Hence, discovering graph-locality metrics will provide insights into redesigning the memory hierarchy to exploit these metrics.  The second topic explores data compression for large complex networks to mitigate the amount of data to move between memories in computing platforms.  Since compression of entire networks is impractical, Dr. Patel will discover techniques for selective compression using graph-locality.  The third topic proposes moving computation closer to the data instead of traditional approaches that require moving data to computation for processing.  This clearly follows the observation that future complex network workloads will be data-access-heavy and not compute-heavy. The research methodology takes a balanced approach with empirical, theoretical and implementation components. The research will result in high-quality publications, and eight HQP will be a direct result of it. They will have expert skills in computer architecture, algorithms, databases, systems, and hardware design.  Canadian industries in computing platform design and big-data software design will greatly benefit.