Prof. Dr. R. Laue WS0001 Informatik I
Übungsblatt 10
Abgabe: 11.1.01 vor der Vorlesung

URL: /axel/informatik1_ws0001_blatt10.html
Dieses Übungsblatt ist in Zweiergruppen zu bearbeiten. Auf dem Blatt bitte den Übungsgruppentag angeben. Um den Übungsschein zu erhalten, muß man 50% der Punkte erreichen und zweimal erfolgreich eine Aufgabe vorrechnen.

Aufgabe 30 - Wabenmultiplizierer (3+3+2+5 Punkte)

In der Vorlesung wurde ein Verfahren zur parallelen Multiplikation mit Ergebnistransport von Matrizen vorgestellt. Dazu werden die Bausteine wabenförmig angeordnet. Zeichnen Sie das schematische Netz zur Multiplikation von zwei 3x3 Matrizen (a_ij) und (b_ij). Es ist zu beachten, dass das Netz leicht auf größere Beispiel zu erweitern ist und daß die Eingaben (Matrizen A und B) nur einmal zur Verfügung stehen. (3 Punkte)
Erläutern Sie die Funktionsweise und zeigen Sie wieviele Schritte bei einer Multiplikation von zwei nxn Matrizen nötig sind. (3 Punkte)
Wieviele Wabenbausteine sind bei einer Multiplikation von nxn Matrizen nötig? (2 Punkte)
Nehmen Sie als ein Beispiel eine 3x3 Matrix, die als Einträge die Ziffern Ihrer Matrikelnummer in zufälliger Reihenfolge und sonst Nullen hat und quadrieren diese mit obigen Netz. Nehmen Sie für jeden Schritt eine Fotokopie Ihres Netzes und tragen Sie die Belegungen der Bausteine ein. (5 Punkte)

Aufgabe 31 - Bitoner Sortierer (4+4 Punkte)

a) Zeichnen Sie das Schaltnetz für den bitonen Sortierer mit 16 Eingängen. (4 Punkte)
b) Sortieren Sie damit das Wort

"WEIHNACHTSFERIEN"

in absteigender Reihenfolge. Nehmen Sie dazu eine Fotokopie Ihres Schaltnetzes und tragen SIe die Belegung in den einzelnen Schichten ein. (4 Punkte)

Aufgabe 32 - Aufwand (3 Punkte)

In der Vorlesung wurde eine Tabelle aufgestellt zur Abschätzung der Rechenzeit bei einem Prozessor mit 1000 Operationen pro Sekunde. Erweitern Sie diese Tabelle um drei Spalten (1 sec/1 min/ 1 h) für einen Prozessor mit 1 Million Operationen pro Sekunde.