DE68907383T2

DE68907383T2 - Verfahren und Anordnung zur Umsetzung von Umrissdaten in Rasterdaten.

Info

Publication number: DE68907383T2
Application number: DE89200971T
Authority: DE
Inventors: Robertus Ernestus Jacobs
Original assignee: Oce Nederland BV
Current assignee: Canon Production Printing Netherlands BV
Priority date: 1988-04-29
Filing date: 1989-04-17
Publication date: 1993-12-09
Anticipated expiration: 2009-04-18
Also published as: NL8801116A; JP2825268B2; US5386510A; DE68907383D1; EP0344827A1; JPH01318174A; EP0344827B1

Description

Diese Erfindung betrifft ein Verfahren gemäß Anspruch 1 zur Umsetzung von Daten betreffend die Umrisse vön Bildelementen (Objekten) in Rasterdaten, wobei ein Raster aus einer Anzahl von Abtastzeilen aufgebaut ist, in einer Anordnung mit einer Zentraleinheit, wenigstens zwei parallelen Prozessoren, die jeweils mit einem lokalen Bitfeldspeicher versehen sind, der in Rasterspeicher-Zeilen unterteilt ist, in denen die entsprechenden Abtastzeilen abgelegt werden können, und mit einem Kommunikationskanal, der die Zentraleinheit und die Prozessoren verbindet, und außerdem betrifft die Erfindung eine Anordnung nach Anspruch 5 zur Umsetzung von Daten betreffend die Umrisse von Bildelementen (Objekten) in Rasterdaten, wobei ein Raster aus einer Anzahl von Abtastzeilen aufgebaut ist, mit:
- einer Zentraleinheit, die dazu eingerichtet ist, eine Rasterumsetzanweisung für wenigstens einen Teil des Objekts zu erzeugen und zu übermitteln,
- wenigstens zwei parallelen Prozessoren, die jeweils mit einer Arithmetik-Logik-Einheit und einem lokalen Bitfeldspeicher versehen sind, der in Rasterspeicher-Zeilen unterteilt ist, in denen die entsprechenden Abtastzeilen abgelegt werden können, wobei die Prozessoren jeweils dazu eingereichtet sind, auf der Grundlage der Rasterumsetzanweisung eine entsprechende Zeichenanweisung zu erzeugen, mit Daten über die Position in dem Bitfeldspeicher, wo das Resultat dieser Zeichenanweisung abzulegen ist, und dieses Resultat in dem lokalen Bitfelspeicher zu speichern,
- und einem Kommunikationskanal, der die Zentraleinheit und die parallelen Prozessoren verbindet.
Eine Anordnung dieser Art ist Teil eines Rasterbildprozessors, wie er in Druckern und visuellen Anzeigeeinheiten verwendet wird, denen Daten über die zu druckenden Zeichen oder Figuren (Objekte) in Form von Umrißbeschreibungen wie etwa Vektorbeschreibungen von einer Verarbeitungsstation zugeführt werden. Das Verfahren zur Umsetzung von Bild-Umrißdaten in Rasterdaten ist aus dem Stand der Technik bekannt, ebenso die Erzeugung und Ausführung von Zeichenanweisungen (vgl. z.B. FOLEY und VAN DAM, Fundamentals of Interactive Computer Graphics, Addison-Wesley (Reading, Massachussets, US), Kapitel 11.2, 11.7 und 12.1). Der Drucker (beispielsweise ein Laserdrucker) ist dazu eingerichtet, einen modulierten Lichtstrahl zeilenweise über eine lichtempfindliche Oberfläche abzulenken. Durch Vorrücken der lichtempfindlichen Oberfläche rechtwinklig zur Ablenkrichtung ist es möglich, eine vollständige Seite bildmäßig zu belichten und nach einem bekannten Verfahren auf ein Empfangsblatt zu drucken. Die Umrißbeschreibungen müssen deshalb zunächst in Rasterdaten umgesetzt werden. Diese Rasterdaten werden in einem seitengroßen Bitfeldspeicher abgelegt. Die Position jedes Bildpunkts auf der lichtempfindlichen Oberfläche entspricht der Position desjenigen Speicherelements im Speicher, wo die Information über diesen Bildpunkt gespeichert ist. Damit ein Hochgeschwindigkeitsdrucker realisiert werden kann, muß ein Hochgeschwindigkeits-Rasterbildprozessor verwendet werden. Ein Beispiel eines solchen Rasterbildprozessors wird beschrieben in WO 87/02159.
Dieser Rasterbildprozessor basiert auf einer Parallelarchitektur. Jeder Bildprozessor verarbeitet einen dauerhaft zugewiesenen Teil (lokalen Speicher) dieses Bitfeldspeichers. Die Umsetzung eines Objektes erfolgt auf der Grundlage dieses lokalen Speichers, der jedem Unterprozessor dauerhaft zugewiesen ist. Ein Unterprozessor empfängt nur den Teil des Objekts, der dem zu diesem Unterprozessor gehörenden lokalen Bitfeldspeicher zugeordnet ist.
Die zum Füllen dieses lokalen Bitfeldspeichers erforderliche Rechenarbeit wird in dem Unterprozessor ausgeführt, der mit diesem lokalen Bitfeldspeicher physisch verbunden ist.
Bei der Umsetzung des Objekts in einem solchen System können drei Tätigkeiten unterschieden werden:
a) Übertragung von Information über das Objekt zu den Prozessoren,
b) Berechnung der Rasterspeicher-Zeilen, die in dem lokalen Speicher zu füllen sind, und
c) Füllen der Rasterspeicher-Zeilen mit einem Bitmuster entsprechend demjenigen Teil des Objekts, das für diesen Teil des Bitfeldspeichers vorgesehen war.
Die Schritte b) und c) werden nur dann von dem selben Unterprozessor ausgeführt, wenn das Füllen des Bitfeldspeichers über diesen Prozessor erfolgen muß.
Unabhängig davon, wie die Rasterspeicher-Zellen des Bitfeldspeichers auf die verfügbaren Unterprozessoren verteilt sind, wird es immer Objekte geben, die so geformt sind, daß nicht jeder Unterprozessor gleichermaßen an der Rasterumsetzung des Objekts beteiligt ist. Dies führt schließlich zu einer ineffizienten Prozessorauslastung, da es dann im Durchschnitt eine gewisse Anzahl untätiger Prozessoren gibt.
Aufgabe der Erfindung ist es, eine effizientere Prozessorauslastung zu erreichen.
Erfindungsgemäß wird diese Aufgabe bei einem Verfahren nach dem Oberbegriff gelöst durch die Erzeugung - wenigstens für einen Teil des Objekts - einer Rasterumsetzanweisung in der Zentraleinheit, die Übertragung dieser Rasterumsetzanweisung über den Kommunikationskanal, die Ausführung dieser Rasterumsetzanweisung durch einen ersten Parallelprozessor, der zu dieser Zeit nicht beschäftigt ist, wobei wenigstens eine entsprechende Zeichenanweisung erzeugt wird, die auch Daten über die Position in dem Bitfeldspeicher enthält, wo das Resultat dieser Zeichenanweisung abzulegen ist, die Übertragung dieser Zeichenanweisung über den Kommunikationskanal und die Ausführung dieser Zeichenanweisung in einem zweiten Parallelprozessor, wobei der lokale Bitfeldspeicher mit Rasterdaten betreffend wenigstens den einen Teil des Objekts gefüllt wird.
Im Hinblick auf die Anordnung wird die Aufgabe erfindungsgemäß gelöst durch eine Anordnung nach dem Oberbegriff, bei der jeder Parallelprozessor mit einer Kommunikationseinheit versehen ist, die abhängig vom Auslastungszustand der Arithmetik-Logik-Einheit eine Rasterumsetzanweisung über den Kommunikationskanal an einen nachfolgenden Parallelprozessor übermittelt. Im Ergebnis kann eine zugeführte, aus Umrißbeschreibungen bestehende Seite schneller umgesetzt und in den Bitfeldspeicher eingeschrieben werden, so daß sich die Druckgeschwindigkeit erhöht.
Diese und andere Vorteile werden nachfolgend unter Bezugnahme auf die Zeichnungen erläutert. Es zeigen:
Fig. 1 ein Diagramm einer Anordnung zur Umsetzung von Daten über die Umrisse von Bildelementen in Rasterdaten,
Fig. 2 ein Diagramm eines Parallelprozessors,
Fig. 3 eine detalliertere Darstellung eines Parallelprozessors gemäß Figur 2,
Fig. 4 ein Diagramm eines Bitfeldspeichers und
Fig. 5 ein Diagramm der Prozesse, die in einem Parallelprozessor ausgeführt werden können.
Figur 1 ist ein Diagramm einer Anordnung zum Umsetzen von Daten über die Umrisse von Bildelementen (Objekten) in Rasterdaten (Abtastzeilen). Eine Zentraleinheit 10 ist mit einer Anzahl von Parallelprozessoren 11,12,13 über einen Kommunikationskanal 20 verbunden. Jeder Parallelprozessor enthält eine Kommunikationseinheit 21 ,22,23, eine Arithmetik-Logik-Einheit 24,25,26 und einen lokalen Bitfeldspeicher 27,28,29.
Jeder lokale Bitfeldspeicher 27,28,29 enthält einen Teil eines seitengroßen Bitfeldspeichers, in dem Bilddaten über eine vollständige Seite gespeichert werden können. Jedes Bild einer Seite mit einer Größe von etwa 20 x 30 cm enthält somit 4000 x 6000 Bildpunkt oder Pixel (20 Pixel/mm). Diese Pixel sind in 4000 Abtastzeilen von jeweils 6000 Pixel Länge angeordnet. Bei n lokalen Bitfeldspeichern enthält jeder lokale Bitfeldspeicher Bilddaten über 4000/n Abtastzeilen. Bei 8 lokalen Bitfeldspeichern und somit 8 Parallelprozessoren wird jeder lokale Bitfeldspeicher Bilddaten von 500 Abtastzeilen enthalten.
Figur 2 zeigt schematisch einen Parallelprozessor 11. Dieser Parallelprozessor 11 enthält eine Kommunikationseinheit 21, die mit dem Kommunikationskanal 20 und mit der Arithmetik-Logik-Einheit 54 verbunden ist. Die Arithmetik-Logik-Einheit 24 ist mit einem lokalen Bitfeldspeicher 27 verbunden. Letzterer ist in eine Anzahl von Rasterspeicher-Zeilen 30-37 unterteilt, von denen jede die Bilddaten für eine Abtastzeile enthalten kann. Somit enthält die Rasterspeicher-Zeile 30 Bilddaten der ersten Abtastzeile, die Rasterspeicher-Zeile 31 enthält Bilddaten der zweiten Abtastzeile, und so weiter. Dieser lokale Bitfeldspeicher 27 kann somit Bilddaten in bezug auf beispielsweise die ersten 8 Abtastzeilen einer Seite enthalten. Ein zweiter Parallelprozessor (nicht gezeigt) ist mit einem zweiten lokalen Bitfeldspeicher versehen, der die Bilddaten der nächsten 8 Abtastzeilen einer Seite enthalten kann, und so weiter.
Wenn eine Rasterumsetzanweisung über den Kommunikationskanal 20 an den ersten Parallelprozessor 11 und die Kommunikationseinheit 21 übermittelt wird, während die Arithmetik-Logik-Einheit 24 nicht in Betrieb ist, so wird diese Rasterumsetzanweisung an die Einheit 24 übermittelt und dort ausgeführt (dies ist schematisch durch einen Block 42 angedeutet). Das Resultat dieser Rasterumsetzanweisung besteht darin, daß wenigstens eine Zeichenanweisung erzeugt wird, wobei diese Zeichenanweisung auch Daten darüber enthält, welche Stelle das so zu erzeugende Bildelement in dem Bitfeldspeicher einnehmen soll. Als Beispiel wird eine Rasterumsetzanweisung ausgewählt, in der ein Objekt in Rasterspeicher-Zeilen entsprechend den Abtastzellen 17-23 plaziert werden muß. Diese Zeichenanweisungen werden dann über den Kommunikationskanal 20 übermittelt. Jede Kommunikationseinheit jedes Parallelprozessors enthält Vergleichsmittel 45, die die Ortsdaten in der Zeichenanweisung mit den Ortsdaten der zu diesem Parallelprozessor gehörenden Rasterspeicher-Zeilen vergleichen. Im Fall der Gleichheit (im gewählten Beispiel trifft dies für den dritten Parallelprozessor zu) wird diese Zeichenanweisung an die zugehörige Arithmetik-Logik-Einheit übermittelt. Falls keine solche Gleichheit vorliegt, wird die Zeichenanweisung an den nächsten Parallelprozessor weitergegeben.
Die Zeichenanweisung wird dann in der Arithemtik-Logik-Einheit ausgeführt (schmematisch angedeutet durch Block 43) und an den Bitfeld-Füller (schematisch angedeutet durch Block 44) übergeben, der die Bilddaten in den korrekten Positionen in den Rasterspeicher-Zeilen des lokalen Bitfeldspeichers 27 plaziert.
Die Arithmetik-Logik-Einheit 24 enthält außerdem Mittel, mit denen der Auslastungszustand der Einheit bestimmt und der Kommunikationseinheit 21 und über diese der Zentraleinheit mitgeteilt werden kann. Wenn in dem Fall, daß eine neue Rasterumsetzanweisung über den Kommunikationskanal 20 übermittelt wird, beispielsweise der erste Parallelprozessor beschäftigt ist, so wird die Rasterumsetzanweisung an den zweiten Parallelprozessor weitergegeben, und so weiter, bis die Anweisung einen nicht beschäftigten Parallelprozessor erreicht. Letzterer führt dann die Rasterumsetzanweisung aus.
Die Ausführung einer Rasterumsetzanweisung braucht daher nicht auf dem Parallelprozessor stattzufinden, auf dem die endgültige Zeichenanweisung auszuführen ist. Folglich wird die Arbeitsbelastung gleichmäßiger über die Parallelprozessoren verteilt.
Damit man eine noch gleichmäßigere Verteilung der Prozesse auf die Parallelprozessoren erhält, können die Rasterzeilen in unterschiedlicher Weise auf die lokalen Bitfeldspeicher verteilt werden. Eine Seite enthält üblicherweise Ränder, in denen keine Bildelemente eingesetzt zu werden brauchen, so daß ein für diesen Bereich vorgesehener Parallelprozessor praktisch keine Zeichenanweisungen auszuführen braucht.
Wenn beispielsweise zehn Parallelprozessoren vorhanden sind, kann der lokale Bitfeldspeicher des ersten Paralleprozessors die Rasterspeicher-Zeilen 1,11,21,31 und so weiter enthalten, der zweite Parallelprozessor enthält die Rasterspeicher-Zeilen 2,12,22,32, und so weiter. Je nach den Seiten-Füllvorgängen, die in speziellen Fällen am häufigsten auftreten, können auch andere Aufteilungen vorteilhaft sein.
Die oben beschriebene Anordnung ist sehr flexibel in der Anwendung. Wenn größere Seiten verarbeitet werden müssen oder eine höhere Auflösung erforderlich ist, können einfach mehr Parallelprozessoren hinzugefügt werden.
In Figur 3 ist ein Parallelprozessor in Form eines Diagramms detallierter dargestellt.
Ein Parallelprozessor dieser Art ist ein "Transputer" Mikrocomputer, der von Messrs Inmos Limited (GB) hergestellt wird, und umfaßt einen Prozessor mit einem Speicher in der Form eines RAM sowie eine Anzahl serieller Kommunikationsschnittstellen für die externe Kommunikation. Der Transputer 50 enthält eine CPU 56 mit einem Nur-Lese-Speicher 55 (ROM) und ist über ein Internes Bussystem 54 mit einer externen Speicherschnittstelle 60, einem internen Lese-/Schreib-Speicher 58 (RAM) und einem internen Nur-Lese- Speicher 59 (ROM) sowie mit einer Anzahl von seriellen Kommunikationsschnittstellen 51 verbunden. Der Transputer 50 enthält außerdem eine Synchronisierschaltung 57. Die Gesamtspeicherkapazität beträgt wenigstens 4 Kilobyte, so daß die CPU 56 ohne externen Speicher arbeiten kann. Die externe Speicherschnittstelle 60 ist über eine Anzahl von Verbindungen 61 mit einem Teil eines Seiten-Bitfeldsystems verbunden. Die Transputer können über die seriellen Kommunikationsschnittstellen 51 zu einem Netzwerk miteinander verbunden sein. Jede serielle Kommunikationsschnittstelle ist mit einer Eingangsleitung 52 und einer Ausgangsleitung 53 versehen, die zusammen den oben erwähnten Kommunikationskanal bilden. Die Arbeitsweise eines Transputers dieser Art wird beispielsweise in der europäischen Patentanmeldung 0 141 660 beschrieben.
Das Verfahren der Umsetzung und der Implementierung des entsprechenden Algorithmus soll anhand eines Beispiels unter Bezugnahme auf Figur 4 erläutert werden. Diese Figur zeigt in Form eines Diagramms ein Bitfeld einer vollständigen Seite, das mit 2000 auf der x-Achse aufgetragenen Rasterspeicherzeilen reproduziert wird. Jede Rasterspeicher-Zeile enthält 2800 Pixel (auf der y-Achse aufgetragen). Die vierhunderste Rasterspeicher-Zeile ist mit x = 400 angegeben. In den folgenden Prozessen bezeichnet der Ausdruck "Äbtastzeile" die Zeile, die zu der Rasterspeicher-Zeile in dem Bitfeld äquivalent ist.
Ein Objekt. beispielsweise ein Dreieck A B C soll in dem Bitfeld gezeichnet und dann vollständig ausgefüllt werden. Die Rasterspeicher-Zeilen des Bitfeldes sind beispielsweise mit vier Parallelprozessoren P1, P2, P 3 und P4 (nicht gezeigt) verbunden.
Der Prozessor P1 ist mit den Rasterspeicher-Zeilen 0,4,8,12,16,20, ... und so weiter verbunden.
Der Prozessor P2 ist mit den Rasterspeicher-Zeilen 1,5,9,13,17, ... und so weiter verbunden.
Der Prozessor P3 ist mit den Rasterspeicher-Zeilen 2,6,10,14,18, ... und so weiter verbunden.
Der Prozessor P4 ist mit den Rasterspeicher-Zeilen 3,7,11,15,19, ... und so weiter verbunden.
Die Eckpunkte A, B und C sind durch die Koordinaten in dem Bitfeld angegeben, z.B. A (400, 1200); B (1200, 1200) and C (800, 2000).
Der Algorithmus umfaßt eine Anzahl von Prozessen, die nachfolgend im einzelnen beschrieben werden sollen. Die Zentraleinheit führt einen Prozeß "schedule" aus. Dieser Prozeß verteilt das aus einer Folge von Zahlen bestehende Objekt auf P1, P2, P3 und P4. Im Fall des Dreiecks A B C lautet der Verteilungsbefehl wie folgt fülle (400, 1200) (1200, 1200) (800, 2000) (-1, -1). Dieser Befehl enthält die Eckpunkte des zu zeichnenden Dreiecks und gibt außerdem an, daß das Dreieck ausgefüllt werden soll. (-1, -1) gibt das Ende des Befehls an.
Figur 5 repräsentiert die Prozesse in einem Parallelprozessor 80 in bezug auf die Prozesse in der Zentraleinheit 81. Der "schedule"-Prozeß 82 verteilt ein Objekt (das beispielsweise von einer Datei stammt) auf die anderen Prozessoren. Dieses Objekt wird gekennzeichnet durch Angabe von Eckpunkten, die durch eine x-Koordinate und eine y-Koordinate gegeben sind. All die x-Koordinaten werden in einer Liste sortiert, und aufeinanderfolgende x-Koordinaten bestimmen ein Interval von Abtastzellen. Jede x-Koordinate bestimmt außerdem für sich eine Abtastzeile, für die separat eine Rasterumsetzung vorzunehmen ist. Die Menge dieser Intervalle und separat umzusetzenden Abtastzeilen bildet die Anweisungen für die anderen Prozessoren. Diese Anweisungen werden an Prozessoren übermittelt, die durch den "schedule"-Prozeß als "nicht beschäftigt" registriert werden, Sobald eine Anweisung an einen Prozessor i gesendet worden ist, wird dieser als "beschäftigt" registriert. Wenn der Prozessor i seine Anweisung ausgeführt hat, übermittelt er ein Signal an "schedule", woraufhin der Prozessor i wieder als "nicht beschäftigt" registriert wird. Solange noch Anweisungen übrig sind, werden diese an Prozessoren übermittelt, die "nicht beschäftigt" sind.
Fünf andere Prozesse laufen auf den Parallelprozessoren P1 bis P4 ab:
der Kommunikationsalgorithmus (com1 und com2) 83,94,
der Abtastzeilenalgorithmus (do. line) 88,
der Trenne-Intervall-Algorithmus (split.interval) 85,
der Zeichne-Intervall-Algorithmus (do.interval) 86 und
der Fülle-Bitfeld-Algorithmus (draw) 87.
Der Kommunikationsprozeß com1 83 auf einem anderen Prozessor kann von einem Links-Prozessor stammende Objekte empfangen und sie lokal speichern und ggf. an einen Rechts-Prozessor übergeben. Er kann eine von "schedule" stammende Rasterumsetzanweisung an den lokalen do.line Prozeß oder den split-interval Prozeß weitergeben, wenn die Anweisung für diesen Prozessor bestimmt war, oder sie an einen Rechts-Prozessor weitergeben. Schließlich kann er eine von einem Links-Prozessor kommende Zeichenanweisung an den lokalen Fülle-Bitfeld-Prozeß draw 87 oder an einen Rechts- Prozessor weitergeben, je nach dem, welcher Prozessor in der Zeichenanweisung adressiert wurde. Er kann eine do.interval Anweisung erhalten, die stets sowohl an den lokalen do.interval Prozeß 86 und an den Rechts-Prozessor weitergegeben wird. Er kann auch eine Zeichenanweisung von dem lokalen do.line Prozeß 88 an einen Rechts-Prozessor und eine do.interval Anweisung von dem split.interval Prozeß 85 weitergeben.
Der Kommunikationsprozeß com2 84 empfängt Zeichenanweisungen von Rechts-Prozessoren und übermittelt sie an einen Links-Prozessor oder den lokalen draw Prozeß 87. Do.interval Anweisungen werden sowohl an den Links-Prozessor als auch an den lokalen do.interval Prozeß 86 weitergegeben. Signale, die anzeigen, daß ein bestimmter Prozessor bereit ist (die sowohl von einem Rechts-Prozessor als auch von dem lokalen do.line Prozeß 88 oder split.interval Prozeß 85 stammen können), werden stets nach links weitergegeben und erreichen schließlich "schedule" 82.
Der Prozeß do.line 88 auf einem anderen Prozessor erhält eine Rasterumsetzanweisung für eine Abtastzeile mit Eckpunkten von dem Kommunikationsprozeß und erzeugt Zeichenanweisungen dafür. Diese Zeichenanweisungen gehen entweder an den lokalen Prozeß draw 87 oder an den Kommunikationsprozeß com1 83, um sie an einen Rechts-Prozessor zu senden, oder an com2 84, um sie an einen Links-Prozessor zu senden.
Der Prozeß split.interval 85 auf einem anderen Prozessor erhält eine Rasterumsetzanweisung für ein Intervall und erzeugt zu diesem Zweck neue Rasterumsetzanweisungen do.interval für den lokalen Prozeß do.interval 86, und für die anderen linken und rechten Prozessoren über com1 83 und com2 84. Eine do.interval Anweisung besteht aus einem zusätzlichen Satz von Zahlen, die Indizes der Information über das Objekt repräsentieren, d.h., die Anfangspunkte der Linien, die das zugehörige Intervall schneiden. Da sämtliche Prozessoren über das vollständige Objekt verfügen, ist die Information darin unzweideutig festgelegt. Sämtliche Prozessoren mit ein oder mehr Abtastzeilen im Bereich des Intervalls können nun sehr schnell Zeichenbefehle für den lokalen Prozeß draw 87 erzeugen, indem sie "edge coherence" (Foley) verwenden. Der Prozeß do.interval 86 empfängt eine do.interval Anweisung von dem Kommunikationsprozeß com1 83 oder com2 84 oder von dem lokalen Prozeß split.interval 85, zusammen mit einer Tabelle von Indizes, die angeben, welche Linien des Polygons das Intervall schneiden, und erzeugt daraus Zeichenanweisungen ausschließlich für den lokalen Fülle-Bitfeld-Prozeß.
Der lokale Prozeß draw 87 ersetzt schließlich in dem Bitfeld-Speicher einen Teil, der dem in der Zeichenanweisung spezifizierten Teil der Abtastzeile entspricht.
Mit Bezug auf Figur 4 läuft der Algorithmus wie folgt ab:
1. Eingabe für "schedule": fill (400, 1200) (1200, 1200) (800, 2000) (-1, -1).
2. "schedule" liest das Objekt und kopiert die Beschreibung in die Unterprozessoren P1 bis P4. Während das Objekt kopiert wird, sortiert und unterteilt "schedule" das Objekt in eine Anzahl von Teilen, in diesem Fall:
R1 Abtastzeile x = 400
R2 Intervall x = 401, 799
R3 Abtastzeile x = 800
R4 Intervall x = 801, 1199
R5 Abtastzeile x = 1200.
R1 bis R5 sind die Anweisungen, die "schedule" an die Unterprozessoren weitergibt.
3. "schedule" übermittelt Anweisungen Ri (d.h. irgendeine der Anweisungen R1 bis R5), solange Prozessoren vorhanden sind, die nicht gerade irgendwelche Anweisungen ausführen, oder bis die Anweisungen vollständig ausgeführt sind. Unter der Annahme, daß die Anweisung R1 an P1 gelangt, R2 an P2 gelangt, R3 an P3 gelangt und R4 and P4 gelangt, kann R5 noch nicht übermittelt werden (alle Prozessoren sind mit einer Anweisung beschäftigt). Die vier Prozessoren können gleichzeitig für jeden Teil bestimmen, welche gefüllt werden sollen. Dies führt im Ergebnis zu Zeichenanweisungen.
4. P1 erzeugt die Zeichenanweisung D400, 1200, 1200 (fülle in der Abtastzeile 400 die Pixel 1200 bis 1200). Da die Abtastzeile 400 im Bitfeld P1 liegt, wird sie intern verarbeitet. P2 erzeugt aufeinanderfolgend D401, 1200, 1202, und diese Anweisung wird auf P2 ausgeführt; D402, 1200, 1204 wird von P2 gesendet und von P3 empfangen und ausgeführt; D403, 1200, 1206 wird ebenfalls gesendet und erreicht P3, wird weitergegeben, und erreicht P4, wo sie ausgeführt wird, und so weiter. Gleichzeitig erzeugt P3 D800, 1200, 1200, die schließlich bei P1 ausgeführt wird. P1 und P3 sollten nunmehr fertig sein, so daß einer von ihnen R5 ausführen kann. P4 erzeugt gleichzeitig D801, 1200, 1998, die an P2 gesandt wird, und D802, 100, 1996, die an P3 gesandt wird, und so weiter.
Wann immer ein Prozessor eine Anweisung Ri ausgeführt hat, wird "schedule" hierüber informiert. Wenn alle Ri ausgeführt worden sind, kann das nächste Objekt eingelesen, kopiert und gerastert werden. Alle auftretenden Objekte können dementsprechend schnell in einem Bitfeldspeicher erzeugt werden.
Die Erfindung ist nicht auf die beschriebenen Ausführungsbeispiele beschränkt, und der Fachmann ist in der Lage, zahlreiche Abwandlungen vorzunehmen, die jedoch sämtlich unter den Gegenstand der nachstehenden Ansprüche fallen.

Claims

1. Verfahren zur Umsetzung von Daten betreffend die Umrisse von Bildelementen (Objekten) in Rasterdaten, wobei ein Raster aus einer Anzahl von Abtastzeilen aufgebaut ist, in einer Anordnung mit einer Zentraleinheit, wenigstens zwei parallelen Prozessoren, die jeweils mit einem lokalen Bitfeldspeicher versehen sind, der in Rasterspeicher-Zeilen unterteilt ist, in denen die entsprechenden Abtastzeilen abgelegt werden können, und mit einem Kommunikationskanal, der die Zentraleinheit und die Prozessoren verbindet, mit den folgenden Schritten:

- Erzeugung - wenigstens für einen Teil des Objekts - einer Rasterumsetzanweisung in der Zentraleinheit,

- Übertragung dieser Rasterumsetzanweisung über den Kommunikationskanal,

- Ausführung dieser Rasterumsetzanweisung und Erzeugung wenigstens einer entsprechenden Zeichenanweisung,

- Übertragung der genannten Zeichenanweisung über den Kommunikationskanal

dadurch gekennzeichnet, daß die genannte Ausführung durch einen ersten Parallelprozessor erfolgt der zu dieser Zeit nicht beschäftigt ist,

und daß die erzeugte Zeichenanweisung auch Daten über die Position in dem Bitfeldspeicher (27, 28, 29) enthält, wo das Resultat dieser Zeichenanweisung abzulegen ist, und in einem zweiten Parallelprozessor ausgeführt wird, wobei der lokale Bitfeldspeicher (27, 28, 29) mit Rasterdaten betreffend wenigstens den einen Teil des Objekts gefüllt wird.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß eine Anzahl von Eckpunkten für jedes Objekt definiert wird.

3. Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß eine Rasterumsetzanweisung für jeden Eckpunkt des Objekts und für jeden zwischen zwei Eckpunkten liegenden Bereich erzeugt wird.

4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, daß die Eckpunkte zu einer Folge entsprechend ihrer Position rechtwinklig zu den Abtastzeilen sortiert werden.

5. Anordnung zur Umsetzung von Daten betreffend die Umrisse von Bildelementen (Objekten) in Rasterdaten, wobei ein Raster aus einer Anzahl von Abtastzeilen aufgebaut ist, nach einem der Ansprüche 1 bis 4, gekennzeichnet durch:

- eine Zentraleinheit, die dazu eingerichtet ist, eine Rasterumsetzanweisung für wenigstens einen Teil des Objekts zu erzeugen und zu übermitteln,

- wenigstens zwei parallele Prozessoren, die jeweils mit einer Arithmetik- Logik-Einheit und einem lokalen Bitfeldspeicher versehen sind, der in Rasterspeicher-Zeilen unterteilt ist, in denen die entsprechenden Abtastzeilen abgelegt werden können, wobei die Prozessoren jeweils dazu eingerichtet sind, auf der Grundlage der Rasterumsetzanweisung eine entsprechende Zeichenanweisung zu erzeugen, mit Daten über die Position in dem Bitfeldspeicher, wo das Resultat dieser Zeichenanweisung abzulegen ist, und dieses Resultat in dem lokalen Bitfelspeicher zu speichern,

- und einen Kommunikationskanal, der die Zentraleinheit und die parallelen Prozessoren verbindet, wobei

jeder Parallelprozessor (11, 12, 13) mit einer Kommunikationseinheit (21, 22, 23) versehen ist, die abhängig vom Auslastungszustand der Arithmetik- Logik-Einheit (24, 25,26) eine Rasterumsetzanweisung über den Kommunikationskanal (20) an einen nachfolgenden Parallelprozessor übermittelt.

6. Anordnung nach Anspruch 5, dadurch gekennzeichnet, daß jede Kommunikationseinheit (21,22,23) Vergleichsmittel enthält, denen Daten über die Position der Rasterzeilen in dem lokalen Bitfeldspeicher (27,28,29) zugeführt werden können, die darin mit den Ortsdaten in einer Zeichenanweisung verglichen werden, und wobei im Fall der Gleichheit die Zeichenanweisung der Arithmetik-Logik-Einheit (24,25,27) zugeführt wird.

7. Anordnung nach Anspruch 5, dadurch gekennzeichnet, daß jeder lokale Bitfeldspeicher (27,28,29) eine Anzahl von Rasterspeicher-Zeilen enthält, die dazu eingerichtet sind, eine Anzahl von Abtastzeilen aufzunehmen, die nicht-zusammenhängend über das Bild verteilt sind.