Project

Back to overview

Hardware-Accelerated Recursive Programs

English title Hardware-Accelerated Recursive Programs
Applicant Atasu Kubilay
Number 172610
Funding scheme Project funding (Div. I-III)
Research institution IBM Research GmBH Cognitive Computing and Industry Solutions
Institution of higher education Companies/ Private Industry - FP
Main discipline Information Technology
Start/End 01.04.2019 - 31.03.2023
Approved amount 262'964.00
Show all

Keywords (5)

Parallel Computing; Hardware Acceleration; Backtracking; Computer Architecture; Recursion

Lay Summary (German)

Lead
HARP - Hardware-Accelerated Recursive ProgramsRekursive Programme mit HardwarebeschleunigungViele Probleme der Datenanalytik im Big-Data-Bereich können mit rekursiven Programmen gelöst werden. Beispiele dafür sind Text-Mining und Graph-Mining (d.h. das Auffinden von typischen Mustern und Gemeinsamkeiten in riesigen, unstruktierten Datensätzen). Rekursive Programme sind logisch aufgebaut, dennoch ist ihre effiziente Parallelisierung schwierig. Bislang existiert keine Standardrechnerarchitektur zur Unterstützung des für Rekursion typischen sog. MIMD-Parallelismus, bei dem gleichzeitig mehrere Operationen auf verschiedene Datenströme (multiple instructions, multiple data) angewendet werden.
Lay summary

Inhalt und Ziel des Forschungsprojektes

Unser übergeordnetes Ziel ist die Definition und Ausarbeitung einer neuartigen Architektur für Rechnerprozessoren, die sich speziell zur parallelisierten Bearbeitung verschiendenster Problemstellungen im Bereich Datenanalytik für Big Data eignen.  Im Besonderen ist unser Ziel eine neue, skalierbare und kostengünstige Rechnerarchitektur, die leistungsstarke Algorithmen mittels paralleler Rekursion mit grosser Effizienz verarbeiten kann.  Dafür haben wir folgende Einzelziele formuliert: (i) Nachweis einer signifikanten Verbesserung der Verarbeitungsgeschwindigkeit anhand ausgewählter Problemstellungen aus der Text- und Graphenanalytik durch das Design von spezialisierten Architekturen für parallele Rekursion. (ii) Die Entwicklung von formalen Modellen, Simulationswerkzeugen und Compilern zur Erforschung und Verbesserung der Designs.

Wissenschaftlicher (und gesellschaftlicher) Kontext des Forschungsprojekts

Rechnerarchitekturen, die speziell für parallele Rekursion konzipiert werden, können die Nachteile und Einschränkungen von Architekturen mit Standardprozessoren vermeiden und somit die für Rechenzentren und mobile Anwendungen notwendige Energieeffizienz erreichen.  Solche Architekturen eignen sich besonders dazu, ein integraler Teil von kosten- und energieoptimierten zukünftigen Rechenzentren und Cloud-Computing-Plattformen zu werden, welche verschiedenste Akzeleratoren umfassen, die jeweils für die entsprechenden Anwendungsbereiche optimiert sind, wie die Analyse von Text, Sprache, Bildern und Videos, sowie Graph-Verarbeitung, maschinelles Lernen und weitere Aspekte künstlicher Intelligenz.

Direct link to Lay Summary Last update: 16.06.2017

Responsible applicant and co-applicants

Employees

Name Institute

Project partner

Abstract

Many Big Data analytics problems can be formulated and solved using recursive (i.e., backtracking) programs. Examples include text mining (e.g., deep parsing) and graph mining (e.g., community detection). Although recursive programs are concise, they are hard to parallelize and exhibit limited single-thread performance and single-instruction multiple-data parallelism. Computer architectures that are specifically designed to support parallel recursion can overcome the performance limitations of general-purpose architectures and achieve the energy efficiency required by datacentres and mobile devices.Imagine that we have a recursive search program and a many-core architecture that offers massive parallelism. Assume also that we compile and load the recursive program on one of the cores, and that the program then starts replicating itself on other cores to evaluate independent search paths in parallel. In other words, the program automatically parallelizes itself on the many-core architecture, while the dynamic behaviour of the program creates additional concurrency. Assume also that the many-core architecture is designed such that the latency of self-replication is zero. Neither the operating system nor any programming effort is involved: the architecture dynamically manages itself. In its effort to fully exploit the available parallelism, the architecture releases cores while backtracking and activates them again when needed. Would such an architecture not be an ideal platform for executing your recursive program? However, a cost- and energy-efficient scalable architectural solution for parallel recursion has yet to be discovered. This proposal aims to fill this gap by defining a novel computer architecture that is extremely efficient in parallel recursion. Supporting parallel recursion at scale requires 1) a large number of processing cores that can operate in parallel on independent regions of input data structures; 2) a domain-specific network that interconnects the processing cores and the memory system, and 3) a dynamic scheduling logic that maximizes the utilization of the available processing cores. The proposed research will address questions such as the following: 1) What are the capability and the number of processing cores needed per chip to meet performance goals?2) Is there a scalable memory system architecture that can service all processing cores in parallel?3) What network architecture is needed to enable dynamic scheduling and to achieve maximal utilization?4) How can we virtualize the resulting architecture and enable multiple users and applications to share it?
-