Task scheduler in VHDL

April 2004

Inspiriert zu dieser Idee wurde ich durch das Studium eines Buches über Transputer vor einigen Jahren und das Nachdenken über FPGA Soft-cores, also Prozessoren die als VHDL/Verilog Design Files vorliegen und zuerst in einen FPGA geladen werden müssen um damit Software auszuführen.

So wie schon vor vielen Jahren zusätzliche Hardware in einen Computer eingebaut wurde um das Betriebssystem mit der Speicherverwaltung zu unterstützen, die sogenannte MMU, soll hier eine zusätzliche Hardwareeinheit realisiert werden, die die Hauptteile des Taskschedulers in die Hardware auslagert und so die Taskwechselzeiten massiv verkürzt.

Wie beim Konzept der MMU ist dies nur durch ein Zusammenspiel zwischen der Hardwareeinheit und entsprechender Software im Betriebssystem möglich, der Hardwareeinheit die laufenden Tasks registriert und beim Ende eines Tasks den Zeitpunkt der nächsten Ausführung bekannt gibt.

Das Konzept des Transputers sieht für jeden Task einen separaten Registersatz vor, dadurch wird die sonst nötige Zeit um die Register auf dem Stack zu sichern komplett eingespart. Bezahlt wird dies durch zusätzliche Transistoren die je nach Software besser oder schlechter ausgenutzt sind. Bei einem Softcore kann das Konzept viel weiter entwickelt werden.

Dem Compiler kann mitgeteilt werden wie viele CPU Register maximal benutzt werden dürfen. Nach dem Compilieren wird analysiert wie viele Register von jedem einzelnen Task genutzt werden. Diese Information wird zusätzlich zur Taskanzahl genutzt um das Design des Softcores anzupassen, so dass keine ungenutzten Register im FPGA implementiert werden. Das gleiche gilt für Interrupt Service Routinen die nach dem gleichen Konzept unterstützt werden können.

Es wäre durchaus denkbar, nur die zeitkritischen Tasks per Hardware umzuschalten und die übrigen Tasks konventionell in Software mit Sicherung auf dem Stack umzuschalten.

Ursprünglich war die Idee für den Linux Kernel gedacht, ich bin mir aber nicht sicher ob das dort überhaupt machbar bzw. implementierbar ist. Aus meiner jetzigen Perspektive wäre für ein solches vorhaben ein Embedded RTOS besser geeignet als basis, dazu kommt das dort der Zeitgewinn auch mehr Nutzer interessiert bzw. besser ausgenutzt werden kann. Da ECOS sowieso verschiedene Scheduler Typen zur Auswahl bietet und voll konfigurierbar ist, wäre das ein valabler Kandidat für eine Umsetzung dieser Idee.

Die das ursprüngliche Konzept bei den Transputern wurde in der Zwischenzeit wieder aufgenommen. Derzeit sind mir zwei mit Transputern vergleichbare Prozessoren bekannt:

• Propeller von Parallax. Bietet acht unabhängige CPU Cores und einen Hardware Round-Robin Scheduler für alle Cores zusammen. Anstatt acht Registersätze (für acht Tasks) sind gleich die kompletten CPU Cores multipliziert worden. Daruch steht natürlich auch mehr Rechenleistung zur Verfügung, das Die ist aber auch grösser. Propeller Chip Homepage
• Die Entwickler hinter dem Transputer, haben nicht hingenommen, dass ST ihre Technologie im Sande hat verlaufen lassen. Sie haben in der zwischenzeit die Firma XMOS gegründed und aus der Zeit bei Nmos gelernt das die Hauptzielgruppe im Embedded Markt ist und nicht im High Performance Computing. Auch haben sie den Support für die C Programmiersprache verbessert, einer der Hauptgründe wiese Anfang der 90er wenige Firmnen auf Transputer umgestiegen sind. Auch heute ist das mehr Psychologie, weil sowieso alle Algorithmen und die Softwarestruktur auf die CPU Architektur angepasst werden muss.Trotzdem bleiben Vorteile mit dieser Lösung. Homepage der Firma XMOS
• Spacetime FPGA von Tabula. Diese Firma bietet einen FPGA an, der im Time-Division-Multiplex betrieben wird. Also jede Logikzelle wird für acht verschiedene Aufgaben nacheinander genutzt (Also so etwas wie Tasks in Software).