Rechnerstrukturen,,Teil,1 …...technische universität! 22 ! dortmund fakultätfür informatik...

fakultät für informatiktechnische universität dortmund

Rechnerstrukturen, Teil 1

Vorlesung 4 SWS WS 19/20

Prof. Dr. Jian-‐Jia ChenFakultät für Informatik – Technische Universität Dortmund

jian-‐jia.chen@cs.uni-‐dortmund.dehttp://ls12-‐www.cs.tu-‐dortmund.de

-‐ 2 -‐technische universitätdortmund

fakultät fürinformatik Rechnerstrukturen (Teil 1)

TU Dortmund

Übersicht1. Organisatorisches

2. Einleitung

3. Repräsentation von Daten

4. Boolesche Funktionen und Schaltnetze

5. Rechnerarithmetik

6. Optimierung von Schaltnetzen

7. Programmierbare Bausteine

8. Synchrone Schaltwerke

TU Dortmund

7. Programmierbare Bausteine7. Programmierbare Bausteine

1. Einleitung

2. Grundbausteine

3. Realisierung von Monomen und Polynomen

4. PLA als Speicher

5. Software PLAs

TU Dortmund

7.1 EinleitungRealisierung von Schaltnetzen

Gedanken zur Anwendung

1. Problem

2. boolesche Funktion

3. Schaltnetz-‐Entwurf

4. Schaltnetz-‐Realisierung

Realisierungen• hoch-‐integrierte Schaltung

teuer Lohnt sich nur bei großen Stückzahlen.• direkte Umsetzung mit Gattern

umständlich

TU Dortmund

7.1 EinleitungRealisierung mit Gattern

TU Dortmund

Quelle: en.wikibooks.org/wiki/Microprocessor_Design/ALU, Autor: Poil

TU Dortmund

7.1 EinleitungAlternative Realisierung durch

• massenhaft produzierte• darum preisgünstige• nach der Fertigstellung in ihrer Funktion noch beeinflussbare• funktional vollständige• also universelle Standardbausteine

Programmable Logic Array (PLA)

Varianten PAL, PROM, FPGA, . . .(zum Teil eingeschränkte Funktionalität)

TU Dortmund

7.1 EinleitungProgrammable Logic Array (PLA) Datenblatt von Lattice

TU Dortmund

1. Einleitung

2. Grundbausteine

4. PLA als Speicher

5. Software PLAs

TU Dortmund

7.2 GrundbausteinePLA Grundbausteine

Funktional vollständig?

Name Typ 𝒇𝟏 𝒙,𝒚 𝒇𝟐 𝒙, 𝒚Identer 0 y xAddierer 1 x ∨ 𝑦 xMultiplizierer 2 y x ∧ yNegat-‐Multiplizierer 3 y x ∧ 𝑦

TU Dortmund

7.2 GrundbausteinePLA Grundbausteine

Funktional vollständig!• UND-‐Verknüpfung: Typ 2, 𝑓- 𝑥, 𝑦 = 𝑥 ∧ 𝑦• ODER-‐Verknüpfung: Typ 1, 𝑓0 𝑥, 𝑦 = 𝑥 ∨ 𝑦• Negation: Typ 3, 𝑓- 1, 𝑦 = 1 ∧ 𝑦 = 𝑦

Name Typ 𝒇𝟏 𝒙, 𝒚 𝒇𝟐 𝒙,𝒚Identer 0 𝑦 𝑥Addierer 1 𝑥 ∨ 𝑦 𝑥Multiplizierer 2 𝑦 𝑥 ∧ 𝑦Negat-‐Multiplizierer 3 𝑦 𝑥 ∧ 𝑦

TU Dortmund

7.2 GrundbausteineAufbau eines PLA

TU Dortmund

7.2 Grundbausteine

PLA für f : {0, 1}𝟑 → {0, 1}

Wie wählt man die Bausteintypen?

TU Dortmund

1. Einleitung

2. Grundbausteine

4. PLA als Speicher

5. Software PLAs

TU Dortmund

7.3 Realisierung von Monomen und PolynomenAuswahl der Bausteine

Feststellung jede Funktion als Polynom darstellbar

Erinnerung Polynom = Disjunktion einiger Monome

Erster Schritt• Wie realisieren wir Monome?• exemplarisch am Beispiel 𝑥1𝑥25 𝑥4

TU Dortmund

7.3 Realisierung von Monomen und PolynomenRealisierung von Monomen

Beispiel: Monom 𝑥1𝑥25 𝑥4

Name Typ 𝒇𝒓 𝒐, 𝒍 𝒇𝒖 𝒐,𝒍Identer 0 𝑙 𝑜Addierer 1 𝑙 ∨ 𝑜 𝑜Multiplizierer 2 𝑙 𝑜 ∧ 𝑙Negat-‐Multiplizierer 3 𝑙 𝑜 ∧ 𝑙

TU Dortmund

Name Typ 𝒇𝒓 𝒐, 𝒍 𝒇𝒖 𝒐,𝒍Identer 0 𝑙 𝑜Addierer 1 𝑙 ∨ 𝑜 𝑜Multiplizierer 2 𝒍 𝒐 ∧ 𝒍Negat-‐Multiplizierer 3 𝑙 𝑜 ∧ 𝑙

x 1 x 1

1 ∧ 𝑥1 = 𝑥1

TU Dortmund

Name Typ 𝒇𝒓 𝒐, 𝒍 𝒇𝒖 𝒐,𝒍Identer 0 𝑙 𝑜Addierer 1 𝑙 ∨ 𝑜 𝑜Multiplizierer 2 𝑙 𝑜 ∧ 𝑙Negat-‐Multiplizierer 3 𝒍 𝒐 ∧ 𝒍

1 ∧ 𝑥1 = 𝑥1

x 1 x 1

x 2 x 2

𝑥1 ∧ 𝑥2 = 𝑥1𝑥2

TU Dortmund

Name Typ 𝒇𝒓 𝒐, 𝒍 𝒇𝒖 𝒐,𝒍Identer 0 𝒍 𝒐Addierer 1 𝑙 ∨ 𝑜 𝑜Multiplizierer 2 𝑙 𝑜 ∧ 𝑙Negat-‐Multiplizierer 3 𝑙 𝑜 ∧ 𝑙

1 ∧ 𝑥1 = 𝑥1

𝑥1 ∧ 𝑥2 = 𝑥1𝑥2

x 1 x 1

x 3 x 3

x 2 x 2

𝑥1𝑥2

TU Dortmund

1 ∧ 𝑥1 = 𝑥1

𝑥1 ∧ 𝑥2 = 𝑥1𝑥2

𝑥1𝑥2

x 1 x 1

2x 4 x 4

x 3 x 3

x 2 x 2

𝑥1𝑥2 ∧ 𝑥4 = 𝑥1𝑥2𝑥4

TU Dortmund

1 ∧ 𝑥1 = 𝑥1

𝑥1 ∧ 𝑥2 = 𝑥1𝑥2

𝑥1𝑥2

𝑥1𝑥2 ∧ 𝑥4 = 𝑥1𝑥2𝑥4

x 1 x 1

2x 4 x 4

x 3 x 3

x 2 x 2

Monomrealisierung• falls Variable fehlt Typ 0• falls 𝑥𝑖 vorkommt Typ 2• falls 𝑥𝑖5 vorkommt Typ 3

TU Dortmund

7.3 Realisierung von Monomen und PolynomenRealisierung von Polynomen

Beobachtung• für f : {0, 1}> → {0, 1}• k verschiedene Monomem1, m2, . . . , mk• in n Zeilen und k Spalten realisierbar

Wie können wir f realisieren, z.B. f = m1∨m2∨m4?

TU Dortmund

Beispiel: Polynom f = m1∨m2∨m4

Name Typ 𝒇𝒓 𝒐, 𝒍 𝒇𝒖 𝒐,𝒍Identer 0 𝑙 𝑜Addierer 1 𝑙 ∨ 𝑜 𝑜Multiplizierer 2 𝑙 𝑜 ∧ 𝑙Negat-‐Multiplizierer 3 𝑙 𝑜 ∧ 𝑙

m1 m2 m3 m4

TU Dortmund

Beispiel: Polynom f = m1 ∨m2 ∨m4

Name Typ 𝒇𝒓 𝒐, 𝒍 𝒇𝒖 𝒐,𝒍Identer 0 𝑙 𝑜Addierer 1 𝒍 ∨ 𝒐 𝒐Multiplizierer 2 𝑙 𝑜 ∧ 𝑙Negat-‐Multiplizierer 3 𝑙 𝑜 ∧ 𝑙

0 ∨ 𝑚0 = 𝑚0

m1 m2 m3 m4

TU Dortmund

Name Typ 𝒇𝒓 𝒐, 𝒍 𝒇𝒖 𝒐,𝒍Identer 0 𝑙 𝑜Addierer 1 𝒍 ∨ 𝒐 𝒐Multiplizierer 2 𝑙 𝑜 ∧ 𝑙Negat-‐Multiplizierer 3 𝑙 𝑜 ∧ 𝑙

m1 m2 m3 m4

0 1 1𝑚0 ∨ 𝑚-

TU Dortmund

𝑚0 𝑚0 ∨ 𝑚-

m1 m2 m3 m4

0 1 1 0𝑚0 ∨ 𝑚-

TU Dortmund

𝑚0 𝑚0 ∨ 𝑚- 𝑚0 ∨ 𝑚-

𝑚0 ∨ 𝑚- ∨ 𝑚A

m1 m2 m3 m4

0 1 1 10

TU Dortmund

Warum ein Grundbaustein für das Weglassen eines Monoms?

𝑚0 𝑚0 ∨ 𝑚- 𝑚0 ∨ 𝑚-

𝑚0 ∨ 𝑚- ∨ 𝑚A

m1 m2 m3 m4

0 1 1 10

TU Dortmund

Warum ein Grundbaustein für das Weglassen eines Monoms?

𝑚0 𝑚0 ∨ 𝑚- 𝑚0 ∨ 𝑚-

𝑚0 ∨ 𝑚- ∨ 𝑚A

0 1 1 10

TU Dortmund

7.3 Realisierung von Monomen und PolynomenPLA: ein konkretes Beispiel

TU Dortmund

7.3 Realisierung von Monomen und PolynomenPLA: ein konkretes Beispiel

TU Dortmund

Beobachtung 1• für f : {0, 1}> → {0, 1}• k verschiedene Monomem1, m2, . . . , mk• in n+1 Zeilen und k Spalten realisierbar

Beobachtung 2• Wir können jede Funktion f : {0, 1}> → {0, 1}B,• für deren Polynom insgesamt k Implikanten ausreichen,• mit einem PLA mit n + m Zeilen und k Spalten realisieren.

TU Dortmund

1. Einleitung

2. Grundbausteine

4. PLA als Speicher

5. Software PLAs

TU Dortmund

7.4 PLA als SpeicherPLA als ROM

Aufgabe: Speichere 2> „Wörter“ der Länge m.

w0 = w0,0w0,1w0,2 ·∙ ·∙ ·∙ w0,m−1 ∈ {0, 1}B

w1 = w1,0w1,1w1,2 ·∙ ·∙ ·∙ w1,m−1 ∈ {0, 1}B

w2 = w2,0w2,1w2,2 ·∙ ·∙ ·∙ w2,m−1 ∈ {0, 1}B

⋮ ⋮ ⋮w2

n−1 = w2

n−1,0w2

n−1,1w2

n−1,2 ·∙ ·∙ ·∙ w2

n−1,m−1 ∈ {0, 1}B

Benutze PLAmit n + m Zeilen, 2> Spalten

Beobachtung m·∙2> Zellen für m·∙2> zu speichernde Bits

mindestens erforderlich

Adressierung mit jeweils n Bits in n zusätzlichen Zeilen

TU Dortmund

7.4 PLA als SpeicherBeispiel

n = 3, m = 6

2D = 8 Wörter

jeweils 6 Bits

TU Dortmund

n = 3, m = 6

2D = 8 Wörter

jeweils 6 Bits

TU Dortmund

n = 3, m = 6

2D = 8 Wörter

jeweils 6 Bits

Beispiel

lies w5

TU Dortmund

n = 3, m = 6

2D = 8 Wörter

jeweils 6 Bits

Beispiel

lies w5

5 = (101)2x2 = 1

x1 = 0

x0 = 1

TU Dortmund

n = 3, m = 6

2D = 8 Wörter

jeweils 6 Bits

Beispiel

lies w5

5 = (101)2x2 = 1

x1 = 0

x0 = 1

TU Dortmund

n = 3, m = 6

2D = 8 Wörter

jeweils 6 Bits

Beispiel

lies w5

5 = (101)2x2 = 1

x1 = 0

x0 = 1

TU Dortmund

n = 3, m = 6

2D = 8 Wörter

jeweils 6 Bits

Beispiel

lies w5

5 = (101)2x2 = 1

x1 = 0

x0 = 1

TU Dortmund

n = 3, m = 6

2D = 8 Wörter

jeweils 6 Bits

Beispiel

lies w5 : 5 = (101)2

x2 = 1 x1 = 0 x0 = 1

AnmerkungPLAs mit festem UND-‐Teil werden als PROM verkauft.

TU Dortmund

7.4 PLA als SpeicherZwischen-‐Fazit PLAs

PLAs sind preiswerte, universelle Bausteine, die• beliebige boolesche Funktionen leicht realisierbar machen,• Minimalpolynomdarstellungenmotivieren,• Speicherung von 2> Wörtern der Länge m in einem

(n + m) × 2> -‐PLA erlauben.

Nachteil nur einmal programmierbar

Wie kann man PLAs beliebig neu programmierbar machen?

TU Dortmund

1. Einleitung

2. Grundbausteine

4. PLA als Speicher

5. Software PLAs

TU Dortmund

7.5 Software PLAsSoftware-‐PLAs

Beobachtung vier verschiedene Typen, mit zwei Bits codierbar

Idee• erweitere PLA-‐Baustein um zwei zusätzliche Eingaben,• die den Baustein-‐Typ codieren

TU Dortmund

Beobachtung vier verschiedene Typen, mit zwei Bits codierbar

Idee• erweitere PLA-‐Baustein um zwei zusätzliche Eingaben,• die den Baustein-‐Typ codieren

Lösung f1 und f2 als Funktionen von (s, t, x, y) darstellen• f1(s, t, x, y) = y ∨ �̅�t x• f2(s, t, x, y) = �̅�x ∨ 𝑡̅𝑥𝑦 ∨ 𝑡𝑥𝑦M

TU Dortmund

7.5 Software PLAsDarstellung von f1 und f2 als Funktionen

Vorgehensweise

Typ 𝒇𝟏 𝒙,𝒚 𝒇𝟐 𝒙, 𝒚0 y x1 x ∨ 𝑦 x2 y x ∧ y3 y x ∧ 𝑦

TU Dortmund

Vorgehensweise

1. Nachdenken über Kodierungen

2. Funktionstabelle

3. KV-‐Diagramm erstellen

4. KV-‐Diagramm bearbeiten

5. Primimplikanten aufstellen

6. Minimale Überdeckung finden

7. Schaltung realisieren

TU Dortmund

• Wir betrachten beide Funktionen getrennt

• 4 unterschiedliche Funktionen• Kodierung der Funktion mittels zwei Bits (s, t)• jede Funktion hat zusätzlich zwei Eingangsvariablen (x, y)• f1 und f2 haben dann jeweils 4 Eingangsvariablen (s, t, x, y)• f1 und f2 haben dann jeweils 1 Ausgangsvariable

TU Dortmund

Vorgehensweise

2. Funktionstabelle

TU Dortmund

2. Funktionstabelle

s t x y 𝒇𝟏0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

s t x y 𝒇𝟏1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

TU Dortmund

Vorgehensweise

2. Funktionstabelle

TU Dortmund

3. KV-‐Diagramm erstellen (1. Hälfte)

s t x y 𝒇𝟏0 0 0 0 0

0 0 0 1 1

0 0 1 0 0

0 0 1 1 1

0 1 0 0 0

0 1 0 1 1

0 1 1 0 1

0 1 1 1 1

TU Dortmund

s t x y 𝒇𝟏0 0 0 0 0

0 0 0 1 1

0 0 1 0 0

0 0 1 1 1

0 1 0 0 0

0 1 0 1 1

0 1 1 0 1

0 1 1 1 1

00 01 11 10

TU Dortmund

00 01 11 10

00 0 0

x y01 1 1

11 1 1

10 0 1

s t x y 𝒇𝟏1 0 0 0 0

1 0 0 1 1

1 0 1 0 0

1 0 1 1 1

1 1 0 0 0

1 1 0 1 1

1 1 1 0 0

1 1 1 1 1

TU Dortmund

00 01 11 10

00 0 0 0 0

x y01 1 1 1 1

11 1 1 1 1

10 0 1 0 0

s t x y 𝒇𝟏1 0 0 0 0

1 0 0 1 1

1 0 1 0 0

1 0 1 1 1

1 1 0 0 0

1 1 0 1 1

1 1 1 0 0

1 1 1 1 1

TU Dortmund

Vorgehensweise

2. Funktionstabelle

TU Dortmund

00 01 11 10

00 0 0 0 0

x y01 1 1 1 1

11 1 1 1 1

10 0 1 0 0

TU Dortmund

00 01 11 10

00 0 0 0 0

x y01 1 1 1 1

11 1 1 1 1

10 0 1 0 0

TU Dortmund

Vorgehensweise

2. Funktionstabelle

TU Dortmund

00 01 11 10

00 0 0 0 0

x y01 1 1 1 1

11 1 1 1 1

10 0 1 0 0

TU Dortmund

00 01 11 10

00 0 0 0 0

x y01 1 1 1 1

11 1 1 1 1

10 0 1 0 0

𝒔𝒕𝒙

TU Dortmund

Vorgehensweise

2. Funktionstabelle

TU Dortmund

00 01 11 10

00 0 0 0 0

x y01 1 1 1 1

11 1 1 1 1

10 0 1 0 0

minimale Überdeckung

𝒇𝟏 𝒔, 𝒕, 𝒙, 𝒚 = 𝒚 ∨ 𝒔𝒕𝒙

𝒔𝒕𝒙

TU Dortmund

Vorgehensweise

2. Funktionstabelle

TU Dortmund

𝒇𝟏 𝒔, 𝒕, 𝒙, 𝒚 = 𝒚 ∨ 𝒔𝒕𝒙

TU Dortmund

Vorgehensweise analog für f2

2. Funktionstabelle

TU Dortmund

Bemerkung zum Einsatz

Beobachtung• für ein n × m-‐PLA werden zur Programmierung• 2nm Bits gebraucht.• Man kann diese 2nm Bits gut in einem PROM speichern.

• einfache und günstige Realisierung von booleschen Funktionen

• besonders geeignet für kleine Stückzahlen

• besonders geeignet bei nur temporärem Gebrauch

TU Dortmund

7.5 Software PLAsVarianten von PLAs

• PAL (ProgrammableArray Logic)• PLA• nur UND-‐Array ist programmierbar• einmal programmierbar

• GAL (Generic Array Logic)• PLA• nur UND-‐Array ist programmierbar• löschbar (UV-‐Licht oder elektrisch)

• CPLD (Complex Programmable Logic Device)• programmierbare AND/OR-‐Matrix• programmierbare Rückkopplung• Ein-‐/Ausgabeblöcke aus Registern

• FPGA (Field ProgrammableGate Array)• ähnlich CPLD, aber beliebige Funktion im Grundbaustein realisierbar

TU Dortmund

1. Einleitung

2. Grundbausteine

4. PLA als Speicher

5. Software PLAs

Rechnerstrukturen,,Teil,1 …...technische universität! 22 ! dortmund fakultätfür informatik...

Documents

64-040 Modul IP7: Rechnerstrukturen fileUniversit at Hamburg MIN-Fakult at Fachbereich Informatik Ubersicht Rechnerstrukturen Modul Rechnerstrukturen: Motivation Das P ichtmodul Rechnerstrukturen

© 2006 W. Oberschelp, G. Vossen Rechneraufbau & Rechnerstrukturen, Folie 11.1

Rechnerstrukturen - Uni Trier · 2013. 8. 18. · LHH L D3 \D3 HLL L D4 \D4 HLH L D5 \D5 HHL L D6 \D6 HHH L D7 \D7. Vorlesung Rechnerstrukturen 9 3.23 C B A Realisierung: Multiplexer

Praktikum Rechnerstrukturen 1 filePraktikum Rechnerstrukturen Bogen 1 1 Einführung und Motivation Ziel des Praktikums Rechnerstrukturen ist die Vertiefung des Verständnis von Funktion

64-040- Modul InfB-RS: Rechnerstrukturen...Beispiel: Apollo 11 (1969) (cont.) 1 Einführung 64-040 Rechnerstrukturen 1. Bordrechner: AGC (Apollo Guidance Computer) I Dimension 61×32×15,0cm

Rechneraufbau & Rechnerstrukturen, Folie 5.1 © 2006 W. Oberschelp, G. Vossen

Rechnerstrukturen, Teil 1 Vorlesung 4 SWS WS 14/15 · technischeuniversität - 2-dortmund fakultätfür informatik Rechnerstrukturen(Teil1) TU Dortmund Übersicht 1. Organisatorisches

Skript zur Vorlesung Rechnerstrukturen, Teil 2” WS 2013/2014 · Skript zur Vorlesung ” Rechnerstrukturen, Teil 2” WS 2013/2014 P. Marwedel, Informatik 12 Technische Universitat

Rechneraufbau & Rechnerstrukturen, Folie 3.1 © 2006 W. Oberschelp, G. Vossen

Rechneraufbau & Rechnerstrukturen, Folie 14.1 © W. Oberschelp, G. Vossen W. Oberschelp G. Vossen Kapitel 14

64-040- Modul InfB-RS: Rechnerstrukturen · Ariane-5 Absturz (cont.) 6.1 Arithmetik - Addition und Subtraktion 64-040 Rechnerstrukturen I Erstﬂug der Ariane-5 („V88“) am 04.Juni1996

© 2006 W. Oberschelp, G. Vossen Rechneraufbau & Rechnerstrukturen, Folie 4.1

Rechneraufbau & Rechnerstrukturen, Folie 6.1 © W. Oberschelp, G. Vossen W. Oberschelp G. Vossen Kapitel 6

Algorithmik kontinuierlicher Systeme - cs10.tf.fau.de · Nxxxx! SS 2017 Interpolation in 1D Prof. U. Rüde - Algorithmik kontinuierlicher Systeme • Alternative 3: Basis aus Newton-Polynomen

Rechnerstrukturen,,Teil,1 …...technische universität! 3 ! dortmund fakultätfür informatik Rechnerstrukturen(Teil 1) TUDortmund 8.,Synchrone,Schaltwerke 8. Synchrone,Schaltwerke

Rechneraufbau & Rechnerstrukturen, Folie 13.1 © 2006 W. Oberschelp, G. Vossen

Rechnerstrukturen - hhgym.de

Polynomial Root Isolation by Michael Arnold. Allgemeines zu Polynomen Ein Polynom vom Grad n hat die Form Es besitzt bei reellen Koeffizienten genau r

wehler/Publications/wehler_comp_alg10.pdf · Einleitung ˆ ˘ˇ ˆ˙ ˝ ˘ˇ Die Kurven und Flächen der Algebraischen Geometrie sind Nullstellengebilde von einem oder mehreren Polynomen

Rechneraufbau & Rechnerstrukturen, Folie 15.1 © 2006 W. Oberschelp, G. Vossen