Browse Prior Art Database

Optimierung von mehrfach verketteten Listen durch verteilte Steuerungseinheiten

IP.com Disclosure Number: IPCOM000017338D
Original Publication Date: 2000-Jul-01
Included in the Prior Art Database: 2003-Jul-25
Document File: 2 page(s) / 26K

Publishing Venue

Siemens

Related People

Thomas Bex: AUTHOR

Abstract

Zeitgemäße, in HW realisierte verkettete Listen bestehen im allgemeinen aus einer zentralen Steuerung, aus einer Queue-Verarbeitungseinheit (bei mehrfach verketteten Listen je eine Queue-Verarbeitungseinheit pro verketteter Liste) und aus dem eigentlichen Speicher, z.B. in Form von einem oder mehreren FIFOs. Die Queue-Verarbeitungseinheit beinhaltet hierbei Head- und Tail-Pointer, z.B. in Form von Registern, und den Up-/Down-Counter zur Queuezustandsindikation.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

-   104   -

Information / Kommunikation

Optimierung von mehrfach verketteten Listen durch verteilteSteuerungseinheiten

Idee: Thomas Bex, Penzberg

Zeitgemäße, in HW realisierte verkettete Listen bestehen im allgemeinen aus einer zentralenSteuerung, aus einer Queue-Verarbeitungseinheit (bei mehrfach verketteten Listen je eineQueue-Verarbeitungseinheit pro verketteter Liste) und aus dem eigentlichen Speicher, z.B.in Form von einem oder mehreren FIFOs. Die Queue-Verarbeitungseinheit beinhaltet hierbeiHead- und Tail-Pointer, z.B. in Form von Registern, und den Up-/Down-Counter zurQueuezustandsindikation.

Der Head-Pointer zeigt auf den nächsten gültigen Eintrag in der zugehörigen Kette, derTail-Pointer auf den nächsten freien Eintrag, in dem ein neuer Wert eingetragen wird. Diezentrale Steuerung übernimmt hierbei den gesamten Verarbeitungsprozess: Steuerung allerQueues (n Queues bei n-fach verketteten Listen), alle Read/Write-Zugriffe auf das FIFOund Aktualisierung aller Queue-Pointer.

Die Steuerung mehrfach verketteter Listen soll hier vereinfacht werden. Ziel ist einedeutliche Performancesteigerung durch Verringerung der kombinatorischen Logiktiefeinnerhalb der Steuerung und eine einfache Erweiterbarkeit der verketteten Listen.

Die Aufgabe wird gelöst, indem man die Steuerung von mehrfach verketteten Listen übereine teilweise verteilte Steuerung realisiert. Hierbei handelt es sich um eine deutlich kleinerezentrale Steuerung mit n dezentralen Steuerungseinheiten (n Steuerungseinheiten bei n-fachverketteten Listen). Die zentrale Steuerung übernimmt hierbei nur die Vergabe vonAufträgen an die einzelnen Queue-Verarbeitungseinheiten (beinhalten nun die dezentraleSteuerung) sowie dessen Rückmeldungen.

Die Queue-Verarbeitungseinheiten überprüfen jetzt eigenständig, welche Aufgabenausgeführt werden müssen, geben die entsprechenden Lese- oder Schreibbefehle inkl.Adressen/Daten über eine zentrale Sammelstelle (Multiplexer) an das FIFO weiter undaktualisieren die Head- und Tail-Pointer.

Da die Steuerung des FIFOs durch die Queue-Verarbeitungseinheiten übernommen werdenund die Durchlaufzeiten durch die Queues bekannt sind, können die Aufträge der zentralenSteuerung sehr fein skaliert werden. Hierdurch werden sehr kurze Verarbeitungszyklenerreicht, bzw. es können sehr viele Ketten verwaltet werden, ohne dass die Steuerung durchRückwirkungen anderer Ketten wie bei der konventionellen Steuerung seh...