Bücher der Reihe Leitfäden und Monographien der Informatik

Dieses Buch entstand aus den Skripten zweier Vorlesungen, die ich im Wintersemester 1979/80 und im Sommersemester 1980 im Fachbereich Angewandte Mathematik und Informatik der Universit~t des Saarlandes gehalten habe. Die zun~chst sehr knappe und an vielen Ste1len eher skizzenhafte Darstellungsform dieser Skripten wurde fur dieses Buch vollig uberarbeitet und besser 1esbar gemacht. Um jedoch die Ubersicht1ichkeit der ursprunglichen Skripten zu bewahren, wurde uberall dort, wo es dem Verst~ndnis forderlich erschien, eine tabellarische oder graphische Darstellung solcher Sachverhalte gew~hlt, die sich anders nur durch lange und umst~ndliche verbale Beschreibungen h~tte realisieren lassen. Das Buch wendet sich vornehmlich an Informatik-Studenten des mittleren Studienabschnitts, etwa vom 3. bis zum 7. Semester. An Kenntnissen wird Erfahr~n~ mit einer beliebigen hoheren Programmiersprache und elnlge Gewohnung an algorithmische Denk­ weise vorausgesetzt. Kenntnisse uber Rechner-Architektur sind zwar fUr das Verst~ndnis nutzlich, aber nicht unbedingt erforderlich, dagegen ist ein gewisses Grundwissen uber Analysis und Statistik sehr von Vorteil. Algorithmen sind in informeller Art in einer ALGOL-~hnlichen Schreibweise dargestellt; auf die Verwendung von System-Programmiersprachen wurde bewuBt verzichtet, da heute noch keine dieser Sprachen so weit verbreitet ist, daB man sie als allgemein bekannt voraussetzen konnte. Ebenso erschien es nicht zweckm~Big, hier eine eigene umfangreiche Beschreibungsmethode zu entwickeln oder erst eine EinfUhrung in eine der bekannteren System-Programmiersprachen (etwa BCPL, Ada oder BLISS) zu geben, da dies zu weit vom eigentlichen Inhalt des Buches weggefuhrt h~tte.

Die beiden Bande "e;Mathematik fur Informatiker"e; , deren ersten wir hiermit vor- legen, beruhen auf einem viersemestrigen Vorlesungskurs, den die beiden Verfasser in den letzten Jahren an der Universitat Paderbom gehalten haben. Die Schwie- rigkeiten einer solchen Vorlesung liegen auf der Hand: Einerseits kann und darf auf mathematische Exaktheit nicht verzichtet werden, andererseits passen -auch wegen der Kurze der zur Verfugung stehenden Zeit -zu komplexe mathematische Begriffe und langwierige Beweise nicht in eine solche Vorlesung. Bei der Planung dieser Vor- lesung versuchten wir, soweit dies moglich war, den algorithmischen Standpunkt in den Vordergrund zu stellen. Bei den Beweisen wurde, wann immer dies moglich war, einer konstruktiven Version der Vorzug gegeben. So enthalt dieses Buch manche Details, die ublicherweise in den Rahmen einer Numerikvorlesung fallen. Nach dem einleitenden Kapitel 1 behandelt Kapitel 2 die Grundlagen der Ma- trizenrechnungj die Kapitel 3 -6 stellen Hilfsmittel aus der Analysis bereit. Kapitel 2 und Kapitel 3 -6 sind voneinander unabhangig und konnen auch in umgekehrter Reihenfolge studiert werden. Zur Zitierweise: Innerhalb eines Kapitels werden die einzelnen Abschnitte in der Form (1.1) zitiert, Formelnummern in der Form (1.1.1). Verweise auf andere Kapitel geschehen in der Form 1(1.1). Am Schlu werden die Lehrbucher aufgefuhrt, auf die im Text hingewiesen wird. Auerdem werden einige Lehrbucher angegeben, die den Stoff dieses Bandes vertiefen.

In den letzten Jahren sind ein Vielzahl neuer Rechnerstrukturen entstanden. Diese unterscheiden sich sehr stark in der Anzahl der Prozessoren, in den Möglichkeiten der Kommunikation und damit auch in der Leistungsfähigkeit. Für den Benutzer solcher parallelen Architekturen wird es immer schwieriger, seine Probleme effizient auf einem bestimmten System zum Laufen zu bringen. Es genügt nicht mehr, einen Algorithmus für eine Problem­ stellung zu finden und zu programmieren. Der Benutzer muß in Kenntnis der Architektur den Algorithmus finden, der auf der ausgewählten Struktur eine effiziente Behandlung der Problemstellung gewährleistet. Es wird immer klarer, daß die Architektur, die Kommunikation und der gewählte Algorithmus als Einheit zu sehen sind. Dieses Buch soll sowohl dem Studenten als auch dem Praktiker eine Einführung in die Hard- und Software von Parallelrechnerarchitekturen geben und ihm ein Gefühl für das notwendige Zusammenspiel der Komponenten Architektur, Kommunikation und Algorithmus vermitteln. Es werden Grundkenntnisse in Rechnerarchitektur und Linearer Algebra für das Verständnis dieses Buches voraus­ gesetzt. VI Mein besonderer Dank gilt den Professoren Dr. U. Herzog, Dr. W. Händler und Dr. W.D. Geyer, die diese Arbeit begutachtet haben. Mein Dank gilt insbesondere auch Frau ehr. Moog, die mit großer Geduld die Bilder für dieses Buch gezeichnet hat. Letztlich gilt mein Dank auch den Herausgebern der Reihe "Leitfäden und Monographien der Informatik" sowie dem Teubner-Verlag, die die Herausgabe dieses Buches ermöglichten.

Ein wichtiges Kriterium zur Beurteilung moderner Rechnersysteme und -netzwerke ist neben der Zuverlässigkeit und Benutzerfreundlichkeit vor allem die Leistung (Performance). Leistungsgrößen aus Anwendersieht sind z.B. die Antwortzeit und die Bearbeitungszeit bestimmter Aufgaben, aus Betreibersieht der Durchsatz und die Auslastung der einzelnen Rechnerkomponenten. Leistungsbewertung wird im wesentlichen beim Entwurf, bei der Auswahl und beim Thning von Rechensystemen durchgeführt: - Durch Vorhersage der Leistungsfähigkeit noch nicht bestehender Systeme kön­ nen neuartige Konzepte und Strukturen untersucht werden. - Durch Ermittlung der Leistung bereits vorhandener Rechenanlagen kann der Anwender die für seine Zwecke geeignetste auswählen. - Durch Erkennen und Beseitigen systeminterner Engpässe kann man gezielte Maßnahmen zur Leistungssteigerung durchführen. Zur Leistungsbewertung werden Meßmethoden und Modellbildungstechniken ein­ gesetzt. Für die Modellbildung von Rechensystemen sind dabei Warteschlangen­ modelle, speziell Warteschlangennetze, die mit Hilfe analytischer Methoden oder simulativ untersucht werden können, besonders geeignet. Dieses Buch, das eine vollständige Neubearbeitung des 1982 in diesem Verlag er­ schienenen Buches "Analyse von Rech~nsystemen" ist, befaßt sich mit der in ihrer Anwendung einfachsten und billigsten dieser Methoden - der analytischen Modell­ bildung. Messungen erfordern teure Meßapparaturen oder Eingriffe ins Systempro­ gramm und können nur bei existierenden Systemen angewendet werden. Simula­ tionen sind sehr zeitaufwendig und damit auch teuer. Aus diesem Grund soll man immer versuchen analytische Modellbildung zur Leistungsbewertung einzusetzen.

DatenfluBrechnerprojekte, die neuesten Entwicklungen von Multithreaded-DatenfluBarchitekturen, die Large-Grain-DatenfluBarchitekturen und weitere DatenfluB-/von-Neumann-Hybridarchitekturen bilden den Kern des Buches. Ein letztes Kapitel behandelt die Multithreaded-von-Neumann-Architekturen und schlieBt damit die letzte Lticke im Architekturspektrum yom DatenfluB- bis zum von­ Neumann-Prinzip.

Dleses Buch habe lch fOr Informatlker, Ingenleure und Mathematlker geschrleben, dle slch mit der Modelllerung und Analyse von komplexen Systemen auf der Grundlage von Petrl-Netzen beschAftlgen oder slch dafOr lnteressieren. Dabel gehe ich auf dle elgentllche Modellblldung nur kurz eln, nlcht nur well dles eln weltes Feld lst, ln dem jeder seine elgenen Erfahrungen machen mu~. sondern well ror den Systementwurf mit Netzen und speziell fUr dle Anwendung von Petrl-Netzen ln der Steuerungstechnlk berelts Buchpubllkatlonen vorllegen. Hauptanllegen dleses Buches lst dle Analyse von Netzmodellen. Wer nlcht iiber dle Ausblldung sondern Ober dle praktlschen BedOrfnlsse selner t?glichen Arbelt mit Petrl-Netzen Freundschaft geschlossen hat, wlrd Netze melst zunAchst als Beschrelbungssprache, also zur Modellblldung angewendet und als nAchsten Schrltt Ablaufslmulatlonen durchgefOhrt haben. Mlt. tels Slmulatlon kann man, lnsbesondere bel durchdachter Anlage der Slmulatlonsexperimente, Fehler lm Entwurf bzw. lm modelllerten System aufspiiren und lhre Ursachen feststellen oder wenlgstens elngrenzen. Man kann aber durch Slmulatlon die Fehlerfrelhelt des Systems nlcht bewelsen, das lst nur durch Analyse mogllch. Um elne Analyse elnes Netzmodells anzulegen und durchzufilhren, slnd theoretlsche Kenntnlsse erforderllch, dle es ermogllchen, rechnergestOtzte Werkzeuge bel der Netzanalyse slnnvoll elnzusetzen und dle Resultate rlchtlg zu lnterpretleren. Dlese Kenntnlsse versuche lch in dlesem Buch zu vermltteln und hoffe, da~ melne Erfahrungen beim Aufbau solcher Programmpakete dabel posltlv "zu Buche" schlagen.

Der Test stellt einen wichtigen Schritt im Entwurfs-und Herstellungsablauf digitaler Schal­ tungen dar, indem er unter Anwendung bestimmter Eingangssignale die Funktion einer ent­ worfenen Schaltung an einem hergestellten Exemplar zu verifizieren erlaubt. Diese Aufga­ bensteIlung gilt gleichermaßen für diskret aufgebaute Logik wie für integrierte Schaltungen. Doch kommt wegen der begrenzten Zahl der externen Anschlüsse bei größeren integrierten Schaltungen fast zwangsläufig die Aufgabe hinzu, Testbarkeitsaspekte beim Entwurf zu berücksichtigen, da andernfalls ein hinreichender Test häufig nicht oder nur mit größeren Schwierigkeiten durchzuführen ist. Das liegt an der "Zugänglichkeit" integrierter Schal­ tungen, die durch die Anzahl externer Anschlüsse beschränkt ist. Aus diesen und anderen Gründen ist der Test digitaler Schaltungen sinnvollerweise zusammen mit Überlegungen zur Testbarkeit einer Schaltung zu sehen. Traditionell ist der Test digitaler Schaltungen um die logische Entwurfsebene herum ange­ ordnet, d.h. daß die logische Ebene den Ausgangspunkt für die Testvorbereitung und die Testdurchführung darstellt. Es gibt darüber hinaus heute auch Ansätze, die von hierar­ chisch höheren Ebenen ausgehen, doch hat sich bisher in diesem Bereich keine allgemein anerkannte Methodik etabliert, wie das für die logische Ebene der Fall ist. Es ist jedoch auch für den Testbereich wichtig, der wachsenden Komplexität der Schaltungen dadurch Rechnung zu tragen, daß man hierarchische Methoden für deren Prüfung einsetzt. Die Notwendigkeit, eine Schaltung zu prüfen, ergibt sich im Rahmen ihrer Entstehung mehrfach, wenn auch mit unterschiedlicher Zielsetzung.