SFB 376

Sonderforschungsbereich 376 - Teilprojekt B5

Algorithmisch spezialisierte Systeme


Inhalt


Mitarbeiter

Leitung

Prof. Dr.-Ing. Jürgen Teich
Fachgebiet Datentechnik
Fachbereich Elektrotechnik und Informationstechnik
Universität Paderborn
Warburger Straße 100
D-33098 Paderborn

Telefon: +49 5251 60-3002
Telefax: +49 5251 60-4221

Wissenschaftliche Mitarbeiter

Dipl.-Inform. Marcus Bednara
Dipl.-Ing. Frank Hannig
Dipl.-Ing. Frank Slomka


Projektbeschreibung

Ungebrochener technologischer Fortschritt in der Miniaturisierung elektronischer Schaltungen hat dazu geführt, dass in wenigen Jahren auf einem Chip 10-100 heutige 16-32Bit-Prozessoren integriert werden können und damit massiv parallele Datenverarbeitung in portablen und anderen eingebetteten Systemen möglich sein wird.

Angekündigte Standards, u.a. UMTS im Mobilfunkbereich und MPEG4 in der Bildverarbeitung werden damit Wirklichkeit, insofern Entwicklungswerkzeuge die inhärente Parallelität der zu implementierenden Algorithmen erkennen und in funktionsfähige und zudem bzgl. Kosten, Geschwindigkeit und Energieverbrauch optimierte Systeme abbilden können. Analysten sehen jedoch voraus, dass in Ermangelung geeigneter Entwurfswerkzeuge die Produktivitätsschere zunehmend auseinander klaffen wird.

Ziel dieses Teilprojektes ist daher die Entwicklung von Entwurfsverfahren für algorithmisch spezialisierte, massiv parallele Systeme (siehe z.B. [TFV+97]) und eine Einbettung einer solchen Entwurfsmethodik in den Entwurf (heterogener) eingebetteter Systeme. Unsere geplanten Arbeiten liegen damit im Themenbereich Targeting verankert, wo wir mit der Erschließsung von Parallelität im Bereich der Hardwareentwicklung bzw. hybrider Hardware/Software-Systeme eine Lücke im Bereich der Entwurfsmethodikprojekte schließen wollen.

Die betrachteten Anwendungsgebiete können charakterisiert werden durch die Notwendigkeit für höchste Rechenleistung bei gleichzeitigen Kosten-, Größen- und anderen physikalischen Beschränkungen. Hierzu gehören insbesondere die Gebiete Bildverarbeitung, Computergraphik, lineare Algebra, Signalverarbeitung und seminumerische Algorithmen.

Die Klasse der betrachteten Algorithmen ist charakterisiert durch statische Parallelität, die damit zur übersetzerzeit vorliegt. Dieser Grad an Parallelität lässt sich direkt aus einem statischen Datenflussgraphen ablesen, der die Eigenschaft aufweist, dass er gebietsweise (stückweise) regelmäßig ist. Für einen gegebenen Algorithmus ist nun eine Abbildung auf eine Schaltung gesucht, die das hohe Maß an inhärenter Parallelität der Spezifikation ausnutzt und ein minimales Maß an Overhead (Steuerung, Kosten, Größe) erzeugt.

Das hier beschriebene und verwendete Algorithmen- und Architekturmodell stellt eine wesentliche Verallgemeinerung der bekannten Konzepte von systolischen Algorithmen und Feldern [KL78, Qui84, Rao85] dar, die von einem homogenen Feld gleichartiger Prozessorelemente ausgehen, die ferner alle die gleiche, zeitinvariante Funktion berechnen.

Während das systolischen Algorithmen zugrunde liegende Berechnungsmodell zu einschränkend ist, bleibt die Notwendigkeit des Entwurfs algorithmisch spezialisierter (Teil-)Systeme ungebrochen. Der Erfolg algorithmisch spezialisierter Architekturen erfordert daher wesentliche Erweiterungen des Algorithmen- und Architekturmodells und der Einbettung solcher Systeme in den Kontext komplexer heterogener Systeme.

Damit einhergehend sind aber neue Aufgaben zu lösen, insbesondere folgende, in diesem Teilprojekt zu untersuchende Forschungsaufgaben:

Forschungsschwerpunkte

  • Abbildungsmethodik

    Untersucht werden sollen neue Verfahren, die auf Algorithmentransformationen basieren. Durch Anwendung einer Sequenz beweisbar korrekter Transformationen wird ein Pfad von stückweisen Verfeinerungen beschrieben, die einen Algorithmus an die Gegebenheiten und Beschränkungen der Zielarchitektur sukzessiv anpassen. Betrachten wollen wir insbesondere die Erforschung von Partitionierungsverfahren von Algorithmen mit affinen Datenabhängigkeiten. Eine Erweiterung von Partitionierungsverfahren auf diese Klasse von Algorithmen ist motiviert durch das Vermeiden zahlreicher Datenpropagationen (=Kopieroperationen) und der damit oft einhergehenden Suboptimalität anschließender Zeittransformationen (Scheduling) im Falle von Algorithmen mit lokalen Datenabhängigkeiten.

  • Optimierung

    Mit dem Ziel der Entwurfsraumexploration unterschiedlicher Implementierungen eines gegebenen Algorithmus wollen wir erstmals die Probleme der Raum- und Zeitabbildung simultan betrachten und Fronten sog. Pareto-optimaler Abbildungen automatisch explorieren. Hier sind diskrete Mehrzieloptimierungsprobleme zu lösen, insbesondere sind Prozessoranzahl, Latenz, Fließbandrate und Effizienz der resultierenden Schaltung für eine gegebene Abbildung zu bestimmen. Ein kürzlicher Durchbruch in der Berechnung der Anzahl von ganzzahligen Punkten innerhalb von konvexen Polytopen durch Bestimmung und Evaluierung sog. Ehrhart-Polynome könnte sich in der Evaluierung von Kostenfunktionen als hilfreich erweisen und soll hier auf die Exploration von Hardwarerealisierungen angewendet werden.

    Weiterhin besteht ein komplexes System nicht nur aus einem Prozessorfeld, sondern ebenfalls aus anderen Komponenten, u.a. Prozessoren, Standardkomponenten, Speichern und Bussen. Algorithmisch spezialisierte Systeme sind daher als Teilsysteme solcher heterogenen Systeme zu verstehen und einzusetzen. Die Potentiale hybrider Implementierungen in Hard- und Software (Hardware/Software Codesign) sollen in Kooperation mit Teilprojekt A1 auf algorithmischer Ebene und mit Teilprojekt A4 konkret für auf elliptischen Kurven basierte Kryptoalgorithmen untersucht werden.

  • Hardwaresynthese

    Beim Hardwareentwurf ist es wichtig, die im Algorithmus inhärente Regelmäßigkeit bis auf Gatterebene beizubehalten. Als Zielarchitektur der Hardwaresynthese wollen wir sog. FPGA (engl. field programmable gate array) betrachten. Existierende kommerzielle Werkzeuge zur Platzierung und Verdrahtung von Schaltungen sind nicht in der Lage, die Regelmäßigkeit auszunutzen, um ein optimales Layout zu generieren. Hier sind theoretische Untersuchungen zur regelmäßigen Platzierung notwendig und Verfahren zur Optimierung von Chipfläche, Latenz, Speicher- und Kommunikationsaufwand.

  • Entwurfssystem

    Für obige Methoden und Optimierungsverfahren soll ein Entwurfssystem entstehen, das einen Pfad vom Algorithmus zur Schaltung erlaubt und die Modelle und erweiterte Abbildungsmethodik ausnutzt, um algorithmisch spezialisierte, massiv parallele Systeme als Teil eines Gesamtsystems zu implementieren.

Kooperationen mit anderen Teilprojekten

Die Betrachtung von regelmässigen parallelen Programmen und Schaltungen und die Einbettung in den Entwurf heterogener Systeme mit dem Entwurfssystem PARO bietet im Themenbereich Targeting interessante Verbindungen zu den anderen Projekten im Bereich der Entwurfsmethodik. Zusammen mit Teilprojekt B1 wurde bereits im Vorfeld der Antragstellung eine erfolgreiche Anknüpfung unseres Werkzeugs zur Entwurfsraumexploration unterschiedlicher Hardware/Software-Lösungen angegangen [BTT98] und erste Ergebnisse veröffentlicht [RHTB00].

Den Nutzen und Erfolg hybrider (gemischt in Software (sequenzieller) und Hardware (massiv paralleler)) Lösungen für berechnungsintensive Probleme wurde am Beispiel für Sortierverfahren im Rahmen der Studienarbeit von O. Beyer [Bey00] und in Zusammenarbeit mit dem Projekt A1 theoretisch untersucht und experimentell verifiziert [BBTW00]. Die Ergebnisse zeigen, dass ein Rechnersystem mit einem von einem FPGA unterstützten Mikroprozessor eine Erfolg versprechende Erweiterung für neue Computergenerationen sein könnte. So konnten auf einem FPGA-Baustein 128 16Bit-Sortiererelemente realisiert werden und Speedupfaktoren bis zu 100 für einen neuen, gemischt in Hardware uns Software arbeitenden Sortieralgorithmus erreicht werden. In Zukunft wollen wir hier mit Teilprojekt A1 weitere Problemstellungen diesbezüglich untersuchen und versuchen, die Komplexität und den Nutzen von hybriden Algorithmen in geeigneten Modellen zu quantifizieren.

Das gleiche trifft für die Kooperation mit Teilprojekt A4 zu, wo spezielle Darstellungen und Implementierungen von Algorithmen der Körperarithmetik im Zusammenhang mit Kryptographieverfahren auf elliptischen Kurven untersucht werden sollen. Dabei soll wiederum ein FPGA-basiertes System entstehen, das als Co-Prozessor zu einem Mikroprozessor in der Lage ist, durch Ausnutzung von Regelmäßigkeit und Parallelität auf Bitebene eine effiziente Körperarithmetik zu realisieren, die von der auf dem Mikroprozessor implementierten Kryptographie-Software genutzt werden kann. Da einzelne Bitoperationen in Software nur sehr ineffizient realisiert werden können, erhoffen wir durch den Einsatz eines solchen Co-Prozessores eine enorme Effizienzsteigerung zu erreichen.

Literatur

[BBTW00]
BEDNARA, M., O. BEYER, J. TEICH, R. WANKA: Tradeoff Analysis and Architecture Design of a Hybrid Hardware/Software Sorter. ASAP00 - Proc. Int. Conf. on Application-Specific Systems, Architectures, and Processors, 299-308, Boston, U.S.A., Juli 2000.

[Bey00]
BEYER, O.: Sortieren in Hard- und Software - Analyse und Synthese. Studienarbeit, Universität Paderborn, Fachbereich Elektrotechnik und Informationstechnik, Fachgebiet Datentechnik, 2000.

[BTT98]
BLICKLE, T., J. TEICH, L. THIELE: System-Level Synthesis Using Evolutionary Algorithms. J. Design Automation for Embedded Systems, 3(1):23-58, Januar 1998.

[KL78]
KUNG, H.T., C.E. LEISERSON: Systolic arrays for VLSI. SIAM Sparse Matrix Proceedings, 245-282, Philadelphia, 1978.

[Qui84]
QUINTON, P.: Automatic synthesis of systolic arrays from uniform recurrent equations. The IEEE/ACM 11-th Annual Int'l Symp. on Computer Architecture, 208-214, Ann Arbor, MI, USA, 1984.

[Rao85]
RAO, S. K.: Regular iterative algorithms and their implementations on processor arrays., Stanford University, 1985.

[RHTB00]
RETTBERG, A., W. HARDT, J. TEICH, M. BEDNARA: Design Space Exploration on System Level for Embedded Systems. Proc. of the Ninth Annual International HDL Conference and Exhibition (HDL Conf. 2000), San Jose, U.S.A., März 2000.

[TFV+97]
THIELE, L., J. FORTES, K. VISSERS, V. TAYLOR, T. NOLL, J. TEICH (EDS.): Proc. IEEE Int. Conference on Application Specific Systems, Architectures, and Processors. IEEE Press, Los Alamitos, California, 1997.


Veröffentlichungen


Falls Sie Probleme, Fragen, Anregungen oder Anmerkungen hinsichtlich der Arbeit dieses Teilprojekts des Sonderforschungsbereichs haben, können Sie uns eine Nachricht hinterlassen.


Navigationshilfe:


Frank Hannig, April 2003