Seite 1 von 1

Erste Beispielaufgabe zur Klausur mit FIFOs

Verfasst: 17. Jul 2015 17:53
von joneswack
In der ersten Beispielaufgabe für eine Klausur, die am Dienstag vorgeführt wurde, sollte man ja eine FIFO angeben, die den Datenstrom möglichst speichereffizient aufnehmen kann.

Die vorgeschlagene Bypass FIFO macht natürlich Sinn, weil sie die Daten direkt nach der Aufnahme weitergeben kann.

Könnte man hier aber nicht auch einfach eine ganz normale FIFO verwenden?

Ich stelle mir das Ergebnis dann so vor:
Takt 1: fifo.enq(4)
Takt 2: let val = fifo.first(); fifo.deq(); fifo.enq(5); // val = 4
Takt 3: let val = fifo.first(); fifo.deq(); fifo.enq(42); // val = 5
Takt 4: let val = fifo.first(); fifo.deq(); // val = 42

Hier würde also auch nie mehr als ein Wert in der FIFO gespeichert werden, weil {first,deq} < enq.
Habs auch mal ausprobiert und kompiliert. Scheint so zu laufen.

Der einzige Nachteil gegenüber der Bypass FIFO wäre hier, dass der gerade eingereihte Wert nicht noch im selben Takt verarbeitet werden kann oder?

Re: Erste Beispielaufgabe zur Klausur mit FIFOs

Verfasst: 17. Jul 2015 18:37
von milton
Hab das eben gerade auch mal kurz implementiert und komme zum gleichen Ergebnis. War erst etwas verwundert, weil ich dachte eine mkFIFO hat nur einen Platz, allerdings hat sie 2 und nur die Bypass/Pipeline FIFO hat lediglich einen Platz.

Will man die FIFO auf einen Platz reduzieren bräuchte man allerdings so etwas wie eine PipelineBypassFIFO. Eine normale Bypass oder Pipeline FIFO braucht meiner Meinung nach immer noch 2 Plätze ist dafür aber einen Takt schneller.

Die "Rechenfunktion" verdoppelt einfach nur den Wert.

mkFIFO

Code: Alles auswählen

Put Data: (1). Time (10)
Put Data: (2). Time (20)
Put Data: (3). Time (30)
Finished, Result: (2). Time (30)
Pausing. Time: (40)
Pausing. Time: (50)
Finished, Result: (4). Time (50)
Pausing. Time: (60)
Put Data: (7). Time (70)
Finished, Result: (6). Time (70)
Put Data: (8). Time (80)
Put Data: (9). Time (90)
Finished, Result: (14). Time (90)
Pausing. Time: (100)
Pausing. Time: (110)
Finished, Result: (16). Time (110)
Pausing. Time: (120)
Put Data: (13). Time (130)
Finished, Result: (18). Time (130)
Put Data: (14). Time (140)
Put Data: (15). Time (150)
Finished, Result: (26). Time (150)
Finished, Result: (28). Time (170)
Finished, Result: (30). Time (190)
mkSizedBypassFIFO(2)

Code: Alles auswählen

Put Data: (1). Time (10)
Put Data: (2). Time (20)
Finished, Result: (2). Time (20)
Put Data: (3). Time (30)
Pausing. Time: (40)
Finished, Result: (4). Time (40)
Pausing. Time: (50)
Pausing. Time: (60)
Finished, Result: (6). Time (60)
Put Data: (7). Time (70)
Put Data: (8). Time (80)
Finished, Result: (14). Time (80)
Put Data: (9). Time (90)
Pausing. Time: (100)
Finished, Result: (16). Time (100)
Pausing. Time: (110)
Pausing. Time: (120)
Finished, Result: (18). Time (120)
Put Data: (13). Time (130)
Put Data: (14). Time (140)
Finished, Result: (26). Time (140)
Put Data: (15). Time (150)
Finished, Result: (28). Time (160)
Finished, Result: (30). Time (180)

Re: Erste Beispielaufgabe zur Klausur mit FIFOs

Verfasst: 17. Jul 2015 19:01
von joneswack
Also so wie ich das sehe, braucht die FIFO in meinem Beispiel oben nur einen Platz, weil deq ja immer vor enq stattfindet (Präzedenz).
Man könnte die Standardgröße von 2 ja mit einer SizedFifo auf 1 reduzieren.

Falls die Aufgabe allerdings so gemeint ist, dass immer nach 2 Takten Bearbeitung erst ein neuer Wert eingelesen werden kann, braucht man hier wirklich eine Bypass FIFO und die Musterlösung macht für mich wieder Sinn :roll:

Re: Erste Beispielaufgabe zur Klausur mit FIFOs

Verfasst: 17. Jul 2015 21:46
von milton
Meiner Meinung nach ist die Präzedenz hier nicht das Problem, eine mkFIFO kann einfach nicht im gleichen Takt enq und deq ausführen, sofern sie voll oder leer ist. Damit fällt eine einelementige "mkFIFO" schon aus.

Habe meine Implementation auch unter der Annahme gebastelt, dass die Berechnungslogik 2 Takte pro Wert belegt ist und der Rest in der FIFO verweilen muss, sonst bräuchte man die FIFO ja auch gar nicht.

Re: Erste Beispielaufgabe zur Klausur mit FIFOs

Verfasst: 18. Jul 2015 12:38
von moritz31
blöde Frage, was ist eigentlich der Unterschied zwischen ner Pipeline und ner FIFO ?

Re: Erste Beispielaufgabe zur Klausur mit FIFOs

Verfasst: 20. Jul 2015 18:53
von xshisdi32
moritz31 hat geschrieben:blöde Frage, was ist eigentlich der Unterschied zwischen ner Pipeline und ner FIFO ?
Siehe Reference Guide, abschnitt C.2.5.