DE10158784B4 - A method for determining a distance of processor units to at least one reference position in a processor arrangement and processor arrangement - Google Patents

Abstract

A method for determining a distance of processor units to at least one reference position in a processor arrangement having a multiplicity of processor units, wherein each processor unit is coupled via a bidirectional communication interface to at least one adjacent processor unit and messages are exchanged between mutually adjacent processor units,
In which a first message is generated by a first processor unit, the first message containing a first distance information which contains the distance of the first processor unit or the distance of a second processor unit receiving the first message from the reference position,
In which the first message is sent from the first processor unit to the second processor unit,
In which, depending on the distance information, the distance of the second processor unit from the reference position is determined or stored, and
In which a second message is generated by the second processor unit, which contains a second distance information, which indicates the distance of the second processor unit or the distance between the two processor units.

Description

The The invention relates to a method for determining a distance from Processor units to at least one reference position in one Processor arrangement as well as a processor arrangement.

If a processor array having a plurality of processors such has been made that the local position of the individual Processors within the processor arrangement is not known, the individual processors can not be individually addressed.

In front however, the processors need to use the processor array be organized so that the local Determined position of the individual processors within the processor arrangement can be and thus the processors within the processor arrangement to be able to address individually.

The Organization should even in case of errors occurring in the context of Producing the processor arrangement or later failures of one or more processors or one or more connections between the processors.

One An example of such a processor arrangement is in a pixel arrangement with each pixel of the pixel array being assigned a processor, which can drive the pixel. The pixel can be considered an imaging Element configured or as a sensor element, so that the pixel arrangement as a display unit or as a sensor array can be designed.

In a pixel array having a plurality of pixels, in particular in a large-scale dot-matrix display unit or a large sensor field Often significant problems occur.

A such pixel arrangement has, for example, in the case that it is set up as a so-called "electronic newspaper", per page several million pixels, that is pixels, on.

in the Below, a pixel array becomes a homogeneous pixel matrix understood, which of its edges is addressed or addressed. Such a display matrix or a sensor matrix, that is in general, such a pixel arrangement, for example, active non-linear selectors such as thin film transistors (Thin Film Transistors, TFTs) in Liquid Crystal Display Units (Liquid Crystal Displays, LCDs), which limits their size or dimensionality are due to the characteristics of the thin-film transistors as well as through the parasitic resistors the data lines, which for transmission the signals from and to the individual pixels are used.

In practice, the thin film transistors must have a current ratio between the current flowing in a turn-on state (I _on ) to the current flowing in a turn-off state (I _off ) of 10 ⁵ to 10 ⁶ . High electrical resistances of the very thin and very long data lines in such a pixel arrangement as well as a low current in the power-on state limit the access time to individual rows or columns of the pixels usually arranged in a matrix in the pixel arrangement.

This leads to a very slow electrical charge of the individual pixel elements. Further leads too high a current at a turn-off state of the pixel array in a row-wise or column-wise scanning of the matrix-shaped pixel arrangement to a charge loss of electric charges in the pixel capacitors, if not currently selected are. For this reason, a drive cycle, that is, a time interval, between each of which a control of the individual pixel elements in the pixel arrangement, not too long.

The The above problems are for example in [1] and in [2] im Related to the design of liquid crystal display units or electrophoretic display units with thin-film transistors as drive transistors explained.

Further is the manufacturing process of liquid crystal flat panel displays extremely expensive and prone to failure.

The problems described above are exacerbated in large-area and flexible displays, that is, in large-scale and flexible display units such as an electronic Zei tion, in particular for the case that are used for the switching elements cost-effective production processes such as printing process for the production of printable transistors, for example, in the field of polymer electronics. Such transistors typically have a ratio of I _on / I _off of 10 ⁴ to 10 ⁵ . In any case, the transistors realized in polymer electronics are even worse in their properties than conventional silicon-based thin-film transistors. However, such polymer electronics transistors are only suitable for display units with a few hundred image lines or image columns.

One special problem is the fact that the yield at the production of a pixel array due to the very large area less becomes. This is on the higher Error probability in such a manufacturing process lead back. Different expressed this means that the number of defective pixels or image areas or faulty sensor points, that is, sensor elements becomes larger with increasing area the pixel arrangement.

In handling a very thin, flexible and possibly large display unit is also the probability of the appearance of new defects or damage while handling high. In a conventional addressing of a matrixform Pixel arrangement would a defect in the matrix immediately leads to a line error or column error to lead or it would even a whole area of the pixel arrangement fails.

Out [4] a parallel data processor is known in which both the Information of a data transmitter PE and a data receiver PE as well as the discrimination numbers (transmission line number) be stored in every PE.

Out [5] is a processor array and method for parallel data processing in which an array of processor elements has multiple instruction streams and multiple data streams, which are sent to all processor elements.

Out [6] is an efficient scheme for embedding a complete binary tree architecture into a two-dimensional array of processor elements.

The problems described above have been attempted in accordance with the prior art by improving the characteristics of the selection transistors, that is to say in particular the ratio of I _on to I _off , as well as improved production methods. A protection against mechanical stress on a flat screen was tried by an appropriate housing or by a special packaging to achieve.

Of the The invention is based on the problem, a method for determining a distance from processors to at least one reference position in a processor arrangement and to indicate a processor arrangement, in which or at least part of the above-mentioned problems of the prior art can be reduced.

The Problem is by the method as well as by the pixel arrangement with the Characteristics solved according to the independent claims.

In a method for determining a distance of processor units to at least one reference position in a processor arrangement having a multiplicity of processor units, each processor unit is coupled via a bidirectional communication interface to at least one processor unit that is adjacent to it. The processor units exchange electronic messages with one another, in particular between processor units which are directly adjacent to one another. According to the method, a first message is generated by a first processor unit which is located at the at least one reference position. The first message contains a first distance information which contains the distance of the first processor unit or the distance of a second processor unit receiving the first message from the reference position. The first message is transmitted from the first processor unit to the second processor unit. Depending on the first distance information, the distance of the second processor unit from the reference position is determined or stored. The second processor unit generates a second message which contains a second distance information which contains the distance of the second processor unit or the distance of a third processor unit receiving the second message from the reference position. The second message is transmitted from the second processor unit to the third processor unit. Preferably, the transmission of the respective messages is always via the bidirectional communication interface of the respective immediately adjacent processor units. Depending on the second distance information, the distance of the third processor unit from the reference position is determined or stored. The storage preferably takes place locally in a local memory which is assigned to a respective processor unit. The method steps described above are carried out in an iterative manner for all processor units in the pixel arrangement.

The Reference position can basically be any, preferably the reference position is a position at which a portal processor described below is located, which drives the processor units in the processor arrangement and communication from outside the processor arrangement triggers. The Reference position may further include a position within the processor array be, in which case preferably a processor unit the reference position is arranged and associated with it. Preferably In this case, the reference position is at the edge, i. at the top or bottom line or the left or right Column for the case that the processor units in the processor array in matrix form in Lines and columns are arranged. The transmission of information in or out of the processor arrangement takes place preferably by means of the portal processor exclusively via at least a part of the located at the edge of the processor array Processor units.

clear this procedure means that starting from an "initiation processor unit" at the reference position usually at the edge of the processor arrangement, that is, at one with respect to the Processor arrangement outer pixels, a first distance is assigned, for example, the distance value "1", where indicated will that the preloading processor unit a distance "1" from the portal processor having. For the case that in each case the distance of the the message sending processor unit from the reference position inserted into the message is transmitted to the processor unit to be received the message is, is from the first processor unit, the distance value "1" to the second processor unit transmitted in the first message and the second processor unit becomes the received distance value incremented by a value of "1" incremented value "2" is now called updated second distance value of the second processor unit saved. The second distance value is incremented by a value "1" and a third distance value is generated and transmitted to the third processor unit and saved there. The appropriate procedure is for all processor units carried out in a similar manner and the distance value associated with each processor will decrease Receiving a message with a distance information always updated if the received distance value is smaller than that stored distance value.

A Processor arrangement has a plurality of processor units. Each processor unit is over a bidirectional communication interface with at least one coupled to their neighboring processor unit. To determine the respective Distance of a processor unit of the processor arrangement from a reference position messages are exchanged between the respective processor units, preferably between adjacent processor units, wherein each message contains a distance information which the distance of a processor unit sending the message or a processor unit receiving the message from the reference position indicates (also referred to as the distance value) and wherein each processor unit is set up such that from the distance information of a received message the own distance to the reference position can be determined or stored.

The The invention can be clearly seen in that the according to the state the technology provided global and direct processor control over column and row wirings is abandoned.

by virtue of the use of only local information and exchange electronic messages in particular between each other directly neighboring processors, the approach is very robust towards occurring disorders and failures individual processor units or individual connections between two processor units.

The pixel array, preferably the matrix pixel array, is partitioned into certain areas, for example, image blocks, and each area is assigned an information processing unit, the pixel processor. The region may contain a pixel or a sensor or a plurality of pixels or sensors, which are each driven by a processor unit. Preferably, the processors are distributed in a coarser grid than the pixels or sensors themselves, which clearly corresponds to a spatial subsampling. In this way, the problem of wiring and addressing via column lines and row lines in a matrix-like pixel arrangement is mitigated, since the respective lines connecting the processor units to each other and to a pixel arrangement Connect control circuit, according to the invention generous, that is spatially thicker and thus subject to a lower electrical resistance, can be dimensioned. Each pixel group processor controls the corresponding image area independently, for example by means of a passive matrix drive or an active matrix drive. The size of the subdisplay units is preferably chosen such that the above-described problems of slow charging of the pixel elements as well as the very short time duration between two drive cycles do not occur with a given selection device and a given wiring technique. In principle, any routing instructions for the image information to be displayed or the sensor information to be detected can be implemented in the pixel group processors, so that the image information or the sensor information in the form of electronic data transmission can also be used to detect defects in the display, that is to say the pixel display. Arrangement (for example, in a physical destruction such as a punctual defect, holes, cracks, etc.) can be routed around. This leads to an increased defect tolerance of the device according to the invention. According to the invention, a pixel arrangement is thus provided and a method is provided with which it is possible in a very simple manner to determine the distance of a respective pixel from a reference position and thus also the local position of a pixel within the pixel arrangement. The determination is no longer based on global information, but on local information, which are exchanged in the form of messages between two adjacent processor units. In other words, the self-organization distance determination problem is solved based on local message exchange between adjacent processor units. The self-organization method thus has different distributed local uniform algorithms which exchange the respective messages via the respective bidirectional communication interface. In other words, this means that according to the invention the determination of the distance is based on a self-organization on the basis of purely local information.

Under A pixel is according to the invention both an imaging unit, such as a liquid crystal display unit or a polymer electronics display unit or in general any kind from a screen having a plurality of pixels, to understand. Alternatively, the invention may be in a pixel arrangement can be used in the at least part of the pixels as sensor elements are designed, that is the pixel arrangement consists in this case at least partially in a sensor field. This could be, for example also be a screen unit with built-in touchpad, which in particular on several picture tiles, in other words Multiple image areas can be split, with each image area may be associated with a processor unit.

preferred Further developments of the invention will become apparent from the dependent claims. The relate to described embodiments of the invention the inventive method as well as the processor arrangement according to the invention.

According to one Development of the invention is each processor unit with at least coupled to a pixel, so that the pixel of the respective him assigned processor unit is controllable.

According to this Embodiment of the invention are not only the distances of coupled together processor units, but also about it the distances determined the respective pixel. This is an important foundation for a in the context of the representation of image information used routing detailed image information to be displayed on the individual pixels, of which the respective image information is displayed. In appropriate Way, the distance determination of the pixels also forms a basis for a Routing of acquired sensor information from the pixel to the external one Interfaces to, for example, the portal processor.

According to one Another development of the invention is at least part of the pixels each configured as a sensor. In this case, according to the invention, a distance determination for individual Sensor pixel in a large sensor field carried out.

alternative or additionally For example, at least a portion of the pixels may each be an imaging element be designed. In this case, according to the invention, a distance determination for individual Imaging elements in a large-area, preferably matrix-shaped, Display performed.

The Processor units can each arranged in a hexagonal area, in which case each processor unit has six adjacent processor units each each having over a bidirectional communication interface with the processor unit are coupled.

Further can the pixels themselves have a hexagonal shape.

By Use of a hexagonal shape becomes a very high packing density achieved in the respective arrangement.

alternative can the processor units each arranged in a rectangular area in which case each processor unit will each have four adjacent ones Processor units, each having a bidirectional communication interface are coupled to the processor unit.

Further can the pixels themselves have a rectangular shape.

• • falls der Zeilenparameter in der empfangenen Nachricht größer ist als die bisher gespeicherte Zeilennummer der Prozessoreinheit, so wird der eigenen Zeilennummer der Prozessoreinheit der Zeilenparameterwert z der empfangenen Nachricht zugeordnet,
• • falls der Spaltenparameter in der empfangenen Nachricht größer ist als die eigene Spaltennummer der Prozessoreinheit, so wird der gespeicherten Spaltennummer der Spaltenparameterwert der empfangenen Nachricht zugeordnet,
• • falls die eigene Zeilennummer und/oder die eigene Spaltennummer aufgrund der oben dargestellten Verfahrensschritte verändert worden sind, so werden neue Positionsmess-Nachrichten mit neuen Zeilenparametern und neuen Spaltenparametern erzeugt, welche jeweils die Zeilennummer und Spaltennummer der die Nachricht sendenden Prozessoreinheit oder die Zeilennummer und Spaltennummer der die Nachricht empfangenden Prozessoreinheit enthält, und diese werden über die bidirektionalen Kommunikationsschnittstellen an eine jeweilige Nachbar-Prozessoreinheit übertragen.

According to another embodiment of the invention, before determining the distance of the pixel processors from the reference position, the local positions of the processor units within the processor arrangement are determined by starting from a processor unit at a point of introduction of the processor arrangement position detection messages which at least one line parameter z and a column parameter s, which contains the line number or column number of the processor unit sending the message or the row number or column number of the message processor unit within the processor arrangement, are transmitted to adjacent processor units and the following steps are performed by the respective processor unit become:

• If the line parameter in the received message is greater than the previously stored line number of the processor unit, then the line number of the processor unit is assigned to the line parameter value z of the received message,
• If the column parameter in the received message is greater than the processor unit's own column number, the stored column number is assigned the column parameter value of the received message,
• If the own line number and / or the own column number have been changed due to the method steps described above, new position measurement messages are generated with new line parameters and new column parameters, which respectively contain the line number and column number of the processor unit sending the message or the line number and column number the processor unit receiving the message, and these are transmitted via the bidirectional communication interfaces to a respective neighboring processor unit.

By This development is the inventive concept of local communication between further expanded processor units, since already the local Positions of the individual processor units within the processor arrangement according to this Concept based on local position information, which is only from one obtained from the immediately adjacent processor unit Position information results. This allows a very fault-tolerant approach as part of the self-organization of the processor arrangement.

According to one Another development of the invention is in an iterative process the own distance value of the processor unit then changed if the previously stored distance value is greater than that by a predetermined Value increased received distance value in each received message, and in the case that a processor unit changes its own distance value generated this one distance measurement message and send it over all Communication interfaces to adjacent processor units, wherein the distance measurement message each their own distance as distance information contains or the distance value that the received processor unit receives from the Portal processor has.

Of the Distance value can be increased by a predetermined value value across from changed the own distance value be, preferably by the value "1".

embodiments The invention are illustrated in the figures and will be further explained in more detail. In the figures are identical components with identical reference numerals Mistake.

It demonstrate

1 a plan view of a pixel arrangement according to a first embodiment of the invention;

2a to 2d Top views and a sectional view of individual pixels that may be provided in the pixel array, wherein the pixel may have a rectangular shape ( 2a ), a triangular shape ( 2 B ) or a hexagonal shape ( 2c ); 2d shows a sectional view through the in the 2a to 2c represented pixels;

3 a block diagram in which the pixel arrangement with drive device is shown schematically;

4 a plan view of a processor arrangement according to the first embodiment of the invention;

5 a plan view of a processor arrangement according to a second embodiment of the invention;

6 a plan view of a processor unit in hexagonal shape;

7a and 7b a directed graph ( 7a ) as well as an undirected graph ( 7b );

8th a directed tree;

9a and 9b a sketch of a processor arrangement, modeled as an undirected graph ( 9a ) and as a directed graph ( 9b );

10 a sketch of different routing paths as a directed tree with an input node as a root;

11 a sketch of an optimized routing tree;

12a to 12j a sketch of the routing tree

11 at different activation times;

13a to 13f a sketch of the routing tree 11 at different activation times;

14 a plan view of two hexagonal processor units, in which the bidirectional message exchange between the two processor units is shown;

15 a sketch of an incoherent processor unit;

16 a sketch of a coherent processor unit when sending MessKoherenz messages;

17 a sketch of a processor unit, based on the sending of Messposition messages is explained;

18 a sketch of a processor arrangement after positioning of the individual processor units within the processor arrangement;

19 a sketch of a processor unit, on the basis of the sending a MessDistance message is explained;

20 after the distance determination has been carried out, the processor arrangement, wherein the processor arrangement has a multiplicity of introduction processor units at the lower edge of the processor arrangement;

21 a processor arrangement after distance determination, wherein each third processor unit in the bottom line of the processor arrangement is assigned in each case a reference position;

22 a sketch of a processor unit explaining how to receive and send MessOrganize messages;

23 a sketch of a processor unit, showing the organization order for sending a MessChannel message in an even-numbered column within the processor arrangement;

24 a sketch of a processor unit showing the organization order for sending a MessChannel message in an odd-numbered column within the processor array;

25 a sketch of a plurality of processor units, based on the organization and the message exchange via channels, which couple the communication interfaces of the processor units are explained together;

26 a processor arrangement after regular backward organization in the event that all processor units in the bottom line of the processor arrangement, information or can be supplied from or to a portal processor;

27 a processor arrangement after regular backward organization in the event that information can be supplied to or sent to a portal processor every third processor unit in the bottom line of the processor arrangement;

28 a sketch of a processor unit that explains how to receive and send MessCountNodes messages,

29 a sketch of a processor unit explaining how to receive and send MessNodesSize messages,

30 the processor arrangement after determining the throughput of the processor units in the event that all processor units in the bottom line of the processor arrangement, information can be supplied or sent from a portal processor;

31 the processor arrangement after determining the throughput of the processor units in the event that each third processor unit in the bottom line of the processor arrangement information can be supplied to or from a portal processor or can be sent;

32 a sketch of a processor unit used to explain the sending of MessColDistance messages;

33 a sketch of a processor unit, on the basis of the receiving and sending MessBlockToken messages is explained;

34 a sketch of a processor unit, based on the receiving of a MessToken message is represented by an "uncolored" processor unit;

35 the processor arrangement after determination of meander channels in the processor arrangement in the case of token assignment in the event that all processor units in the bottom line of the processor arrangement, information can be supplied to or from a portal processor or can be sent;

36 a sketch of a processor unit, on the basis of the receiving and sending MessDeleteChannels messages is explained;

37 a sketch of a processor unit explaining how to receive and send MessColOrganize messages;

38 the processor arrangement after reorganization in the event that each third processor unit in the bottom line of the processor arrangement can be supplied or can be sent information from or to a portal processor;

39 the processor arrangement after reorganization in the event that all processor units in the bottom line of the processor arrangement to information from or to a portal processor to can be conducted or sent;

40 a sketch of a processor unit, based on the initialization of the initiation processor unit color is explained by means of a MessColDistance message;

41 the processor arrangement after reorganization at a weight g = 0 in the event that all processing units in the bottom line of the processor arrangement information can be supplied to or sent to a portal processor or can be sent;

42 the pixel arrangement after reorganization at a weight g = ∞ in the event that all processor units in the bottom line of the processor arrangement, information or can be supplied from or to a portal processor;

43 a sketch of a processor unit, on the basis of the receiving and sending MessNumbering messages is explained;

44 a sketch of the processor arrangement after numbering in the event that all processor units in the bottom line of the processor arrangement information can be supplied to or from a portal processor or can be sent;

45 the processor arrangement after the numbering in the event that each third processor unit in the bottom line of the processor arrangement, information can be supplied from or to a portal processor or can be sent;

46 a routing table according to an embodiment of the invention;

47 a sketch of a processor arrangement, based on the routing and the representation of pixel data is explained;

48 a sketch of a processor unit explaining how to receive and send MessRetry messages;

49 a sketch of a processor array having a plurality of processor units and a plurality of pixels, wherein each one group of pixels associated with a processor unit;

50 a sketch of a 4 × 4 pixel group and their control by means of a processor unit;

51 an overview of the messages used according to an embodiment of the invention.

1 shows a pixel arrangement 100 according to a first embodiment of the invention.

The processor arrangement 100 is formed according to a so-called "Fluidic Self Assembly" (FSA) from Alien Technology ^™ described in [3].

The processor arrangement 100 has a substrate 101 with a variety of wells 102 on. The substrate 101 according to this embodiment is a thin, flexible plastic film with a plurality of in this punched wells, via which a suspension with a plurality of processor units 103 as computer chips 103 are configured, the size between 50 microns to 1000 microns, are washed in a liquid. The computer chips 103 are also called nanoblocks. The size and shape of the integrated computer chips 103 hereinafter referred to as processor units 103 are denoted corresponding to those of the wells 102 so that the processor units 103 into the wells 102 self-acting, that is self-paced insertion.

This process is schematic in 1 shown. It arises in the manner described above, a field or an array of processor units, which then meshed together, that is, electrically coupled to each other.

The processor arrangement 100 is designed into an image display device, in which the processor units are used to drive the pixels. For this purpose, it is about the formed array of processor units 103 an electro-optical medium (for example luminous, reflective, etc.), preferably a light-emitting medium, to which electrical couplings originate from the corresponding processor units controlling the electro-optical medium 103 be created.

Each processor unit 103 is responsible for, ie, controls, the pixel immediately above it, or for the pixel region lying above it, that is to say a pixel region with a plurality of pixels, which are grouped into a pixel region.

The processor units 103 For this reason, they are also referred to below as pixel processors 103 designated.

It should be noted in this regard that the invention is by no means limited to imaging elements as a processor arrangement or pixel arrangement, but also for a sensor array with a plurality of electrically coupled to one another and via one or more processor units 103 controlled sensors can be used.

It can According to the invention also arrays used, the partial imaging elements and partially Sensor elements included.

The shape of the individual processor units 103 can be configured according to the invention, for example as in accordance with 2a rectangular, as per 2 B triangular, or as per 2c hexagonal.

2d shows a trapezoidal cross section through the respective processor units 103 , The trapezoidal cross-section ensures that the individual pixels are easier and more likely to be in the pits 102 Insert the pixel arrangement self-organizing.

in the Further will be without limitation of generality a pixel arrangement, which as an image-displaying, that is different expressed is designed as an imaging system described.

The image-displaying system 300 according to an embodiment of the invention is in 3 shown schematically in a block diagram.

The imaging system 300 has a source 301 on, which represents the source of the information to be displayed and according to this embodiment, a central processing unit (Central Processing Unit, CPU) includes a graphics processor, sensors or other input devices and optionally other components.

Furthermore, one is with the source 301 electrically coupled display unit portal 302 provided the function of a mediator between the source 301 and also with the Display Unit Portal 302 coupled actual pixel arrangement 303 (which includes the processor array and the pixels). The Display Unit Portal 302 serves according to the invention for generating a trigger, that is to say an initiation signal, according to this exemplary embodiment of an initiation message, for the initialization of the self-organization, as well as the information distribution via introduction processor units in the processor arrangement 303 ,

The processor arrangement 303 has a field of uniform, so-called intelligent pixels or pixel regions, that of processor units 103 and the one with the processor units 103 coupled and from the processor units 103 controlled pixels are formed. The processor units 103 are meshed with each other, that is, each other via each of the processor units 103 associated bidirectional communication interfaces coupled.

Some processor units 103 the multitude of processor units 103 in the pixel arrangement 303 serve as initiating nodes for supplying information from the display unit portal 302 in the processor arrangement 100 the pixel arrangement 303 ,

According to this embodiment, the respective processor - hereinafter referred to as portal processor - of the display unit portal 302 no information about the size and design of the pixel arrangement 303 , Also have the individual processor units 103 or the one with the processor units 103 coupled pixels at the beginning of the process no information about their respective orientation, ie Alignment, or their local position within the processor assembly.

Also the individual pixel processors, that is the processor units, have no information about their own orientation and location, that is, their local position within the processor arrangement.

In an initially explained in detail initialization phase (before the first use of the pixel array 303 or upon a successful reset of the stored information in the pixel array 303 ) the portal processor of the display unit portal 302 a self-organization of the processor arrangement, as will be explained in more detail below.

As part of the self-organization of the processor arrangement learn the processor units 103 the pixel arrangement 303 their position and orientation as well as information paths to the image structure, that is, for supplying image information to be displayed to the respective pixels, which should actually represent the respective image information.

This learning process is performed using messages between each adjacent processor units in the pixel array 303 be replaced. Part of the knowledge that has been learned will be released to the outside, ie to the display unit portal 302 given as much as the display unit portal 302 needed later to get the image information on the right paths and in the right sequence of pixel arrangement 303 supply for displaying an image to be displayed in each case.

For the image structure, that is to say for the procedure for the information distribution of image information to be displayed within the pixel arrangement 303 is the type of image information to consider.

• • Es werden Routing-Wege lediglich zwischen dem Portalprozessor des Anzeigeeinheits-Portals 302 und den einzelnen Pixelprozessoren, das heißt den Prozessoreinheiten der Pixel-Anordnung 303, nicht aber zwischen den Pixelprozessoren untereinander bestimmt.
• • Es liegt ein gleichmäßiges Routing-Aufkommen vor, das heißt pro anzuzeigendem digitalisierten Bild ist jedem Pixelprozessor genau ein Pixeldatum zu übermitteln.
• • Es wird kein globales Wissen über die Gestalt des Netzes, das heißt der Vermaschung der einzelnen Pixelprozessoren innerhalb der Prozessor-Anordnung vorausgesetzt. Die Wahl von Routing-Wegen innerhalb der Prozessor-Anordnung erfolgt auf Basis lokaler Informationen, die zwischen den einzelnen Pixelprozessoren unter Verwendung von elektronischen Nachrichten ausgetauscht werden.

According to these embodiments, single-pixel data for representing a full-frame or difference image, for example in the context of compressed video images, becomes the individual pixels, that is, more specific to the individual pixel processors 103 transfer. For this purpose, each pixel processor 103 from the portal processor of the display unit portal 302 individually addressed. This leads to a routing of the image information required for the representation of image information to the corresponding pixels and thus to the corresponding processor units within the pixel arrangement. Within the framework of the routing of single pixel data, the following peculiarities of the routing problem are to be considered according to the invention:

• Routing paths only occur between the portal processor of the display unit portal 302 and the individual pixel processors, that is, the processor units of the pixel array 303 but not between the pixel processors.
• • There is a uniform amount of routing, which means that each pixel processor must be given exactly one pixel datum per digitized image to be displayed.
• • No global knowledge of the shape of the network, that is, the meshing of the individual pixel processors within the processor array, is required. The choice of routing paths within the processor array is based on local information exchanged between the individual pixel processors using electronic messages.

• • Selbsterkennung der lokalen Positionen der einzelnen Pixelprozessoren innerhalb der Pixel-Anordnung und somit der Gesamtform der Pixel-Anordnung;
• • Selbstorganisation von Routing-Wegen ausgehend von dem Portalprozessor, das heißt dem Prozessor des Anzeigeeinheits-Portals 302 zu jedem Pixelprozessor in der Pixel-Anordnung 303 derart, dass innerhalb einer vorgegebenen maximalen Zahl von Zeittakten jeder Pixelprozessor von dem Prozessor des Anzeigeeinheits-Portals 302 eine elektronische Nachricht zugeführt bekommen kann.

Thus, according to the invention, two phases are to be distinguished in the context of the use of a pixel arrangement according to the invention:
In a first phase, the so-called self-organization, is carried out a

• Self-recognition of the local positions of the individual pixel processors within the pixel array and thus the overall shape of the pixel array;
• • Self-organization of routing paths from the portal processor, that is, the display unit portal processor 302 to each pixel processor in the pixel array 303 such that within a predetermined maximum number of clock cycles, each pixel processor receives from the processor of the display unit portal 302 can receive an electronic message.

In a second phase, the actual use of the pixel arrangement 303 in the context of the representation of image data, the image data from the portal processor to the pixel processors are sent, that is transmitted, whereby the image to be displayed in the pixel array 303 is built.

The pixel processors 103 are, as in 4 illustrated, in the case that they have a rectangular shape, preferably a square shape, respectively, over each side of the quadrangle via one of the four thus provided bidirectional communication interfaces 401 per pixel processor 103 and about it over electrical lines 402 each with the immediate to a respective pixel processor 103 be neighboring pixel processor 103 coupled.

In other words, this means that in each case a message exchange between two directly adjacent pixel processors is possible, but not an immediate, ie direct message exchange over a further distance away as the immediate vicinity of a pixel processor 103 ,

5 shows another embodiment in which each pixel processor 103 has a hexagonal shape and per pixel processor 103 six bidirectional communication interfaces 501 , also on each side, ie side edge, of the respective pixel processor 103 are provided. That is, according to this embodiment, each pixel processor 103 six neighbor pixel processors 103 has, with which the respective pixel processor 103 via a bidirectional communication interface 501 and an electrical line 502 is coupled for the exchange of electronic messages.

In the following, to simplify the illustration of the invention, only the case of the hexagonal form of a pixel processor will be described 103 but without limitation of generality.

• • Pixelprozessoren 103, denen jeweils bis zu sechs bidirektionale Kommunikationsschnittstellen 501 und elektrische Leitungen 502 zugeordnet sind, und
• • bidirektionale Verbindungen, im Weiteren auch als bidirektionale Kommunikationsschnittstelle 501 und der jeweiligen Kommunikationsschnittstelle 501 zugeordnete elektronische Leitung 502, die je zwei Pixelprozessoren 103 oder einen Pixelprozessor 103 und den Portalprozessor miteinander koppeln.

The pixel arrangement 100 thus has two types of individual components:

• • Pixel processors 103 each with up to six bidirectional communication interfaces 501 and electrical lines 502 are assigned, and
• • bidirectional connections, also referred to as bidirectional communication interface 501 and the respective communication interface 501 associated electronic line 502 each containing two pixel processors 103 or a pixel processor 103 and couple the portal processor together.

The hexagonal pixel processor 103 can have six different orientations, as in 6 shown.

• • Eine erste Ausrichtung 0 (Ost) (Bezugszeichen 600), anders ausgedrückt eine Ausrichtung nach rechts,
• • eine zweite Ausrichtung 1 (Nordost) (Bezugszeichen 601), anders ausgedrückt eine Ausrichtung nach rechts oben,
• • eine dritte Ausrichtung 2 (Nordwest) (Bezugszeichen 602), anders ausgedrückt eine Ausrichtung nach links oben,
• • eine vierte Ausrichtung 3 (West) (Bezugszeichen 603), anders ausgedrückt eine Ausrichtung nach links,
• • eine fünfte Ausrichtung 4 (Südwest) (Bezugszeichen 604), anders ausgedrückt eine Ausrichtung nach links unten, sowie
• • eine sechste Ausrichtung 5 (Südost) (Bezugszeichen 605), anders ausgedrückt eine Ausrichtung nach rechts unten.

According to 6 are the individual connections, that means also the individual communication interfaces 501 during the self-organization phase, as will be explained in more detail below, has already been oriented. The connections are numbered according to this embodiment and identified for better understanding with cardinal points, according to this embodiment, the following nomenclature is used:

• • A first orientation 0 (east) (reference number 600 ), in other words an orientation to the right,
• • a second orientation 1 (northeast) (reference numeral 601 ), in other words an orientation to the top right,
• • a third orientation 2 (northwest) (reference numeral 602 ), in other words an orientation to the top left,
• • a fourth orientation 3 (west) (reference numeral 603 ), in other words an orientation to the left,
• • a fifth orientation 4 (southwest) (reference numeral 604 ), in other words an orientation to the left bottom, as well
• • a sixth orientation 5 (southeast) (reference numeral 605 ), in other words a right-down orientation.

According to this embodiment, it is assumed that the portal processor of the display unit portal 302 electrical couplings to pixel processors 103 on only one side of the pixel array 100 having.

By definition, this is the bottom of the pixel array 100 that is to say illustratively the south side, where the couplings are also defined by the southwest side, that is, the fifth orientation direction of the respective pixel processors 103 to run.

It should be noted in this regard that both the positioning and the orientation of the individual lead-in points of information to the pixel processors 103 in the processor arrangement 100 as well as the shape and orientation of each pixel processor 103 in the processor arrangement 100 basically are arbitrary.

• • mit allen Pixelprozessoren 103 der untersten Zeile in Form einer Matrix, das heißt in Zeilen und Spalten, angeordneten Pixelprozessoren 103 der Prozessor-Anordnung 100 elektrisch gekoppelt, oder
• • mit Pixelprozessoren 103 der untersten Zeile der Prozessor-Anordnung in einem vorgegebenen, regulären, das heißt periodischen Abstand, das heißt beispielsweise jedem dritten, fünften, zehnten, etc., Pixelprozessor 103 innerhalb der untersten Zeile der Prozessor-Anordnung.

In different embodiments of the invention, the portal processor is

• • with all pixel processors 103 the bottom row in the form of a matrix, that is arranged in rows and columns, pixel processors 103 the processor arrangement 100 electrically coupled, or
• • with pixel processors 103 the bottom line of the processor array in a given, regular ren, that is periodic distance, that is, for example, every third, fifth, tenth, etc., pixel processor 103 within the bottom line of the processor array.

Although the portal processor knows after the production of the pixel arrangement 303 the number of its connections to the pixel processors 103 in other words, the number of launch points for supplying information to pixel processors 103 within the pixel arrangement 303 but not necessarily the dimension and design of the pixel array 303 and thus the processor arrangement, that is, the actual shape and arrangement of the pixel processors 103 within the processor arrangement 100 ,

It should be noted in this regard that in particular a direction indication, for example the south side, does not necessarily have a straight line within the processor arrangement 100 must represent.

In the sub-method explained below, it is merely necessary to provide that the individual connections between the portal processor and the pixel processors 103 should always take place in the same place, according to this embodiment on the southwest side 604 ,

The individual pixel processors 103 or the compounds, both of which are referred to as a generic term as individual components of the processor arrangement, can assume the following states:

1. error-free:

The respective component of the pixel arrangement works without restrictions.

2nd defect:

The respective component of the pixel array has failed completely. If the component is a processor unit, then all are Declare connections to this processor unit as defective.

3. Unstable:

The Component has partial failures on, for example, one direction works a bidirectional one Connection between the respective processor unit only temporarily (this means she has a loose connection or is methodically wrong for example, a processor sending a wrong message).

in the Further will be for reasons the simpler representation of the invention, the third state not considered, that is a component is either faultless or defective in the following. Therefore, it plays according to these embodiments no matter if a component due to a special form of Pixel arrangement does not exist (ie, for example, a display unit film, which has the shape of a triangle), or the respective component due to a manufacturing defect or due to wear and tear became defective.

In the further explained in the following information transfer, that is the sending of electronic messages between two pixel processors 103 within the pixel arrangement 303 or from the portal processor to a pixel processor 103 at a point of initiation of the pixel arrangement 303 is a clocking of the overall system, that is, the entire pixel arrangement 303 considered.

• • Lesen von einer oder mehreren elektronischen Nachrichten, die an einer oder mehreren Verbindungen, das heißt über eine oder mehrere bidirektionale Kommunikationsschnittstellen des jeweiligen Pixelprozessors anliegen und die im zeitlich vorangegangenen Zeittakt von einem Nachbar-Pixelprozessor versendet wurden.
• • Verarbeitung der empfangenen Nachricht.
• • Gegebenenfalls Versenden von einer oder mehreren Nachrichten über eine oder mehrere Verbindungen und damit über eine oder mehrere bidirektionale Kommunikationsschnittstellen des Pixelprozessors 103, die im zeitlich darauffolgenden, das heißt nächsten Zeittakt von einem Nachbar-Pixelprozessor empfangen werden können.

Every pixel processor 103 in the pixel arrangement 303 is set up so that it can perform the following actions within a time cycle:

• Reading one or more electronic messages which are present at one or more connections, that is to say via one or more bidirectional communication interfaces of the respective pixel processor and which were sent by a neighboring pixel processor at a time-related time interval.
• • Processing the received message.
• • If necessary, sending one or more messages over one or more connections and thus via one or more bidirectional communication interfaces of the pixel processor 103 which can be received by a neighboring pixel processor at the time-following, that is, next-time clock.

Within a time clock thus an electronic message can only from a pixel processor 103 to a neighbor pixel processor 103 be transmitted.

However, it should be noted in this context that according to the invention no global, that is for the entire processor arrangement 100 provided common timing of the pixel processors 103 must exist, but this is adopted for ease of illustration of the invention hereinafter.

in the Further will become easier understanding of the procedure of the invention Basics about explains the mathematical modeling of the pixel arrangement.

Below are the pixel processors 103 and the display unit portal 302 modeled as a directed graph and the routing paths as a directed tree.

The Choice of routing thus results as a discrete optimization problem.

Definition 1 (Judged Graph, undirected graph)

(I)

Given a lot of V and a lot of E. Is g: E → V 2 = V × V an illustration with the components G - : E → V and g + : E → V, ie g: E → V 2 . e ↦ (g - (e), g + (E)), that's the name of the tuple
(V, E, g)
directed graph with vertex set (vertex set) V, edge set E and incidence mapping g. g ^- (e) is called the initial vertex of the edge e ε E and g ⁺ (e) is called the terminating vertex of the edge e ε E.

(Ii)

Given a set V and a set M. Consider the equivalence relation α: = {((x, y), (y, x)) ε V 2 × V 2 ; with x, y ∈ V} ⊆ V 2 × V 2 with the equivalence classes [x, y]: = {(x, y), (y, x)}, for all x, y ε V.

With a picture u: M → V 2 / α = {[x, y]; x, y ∈ V} is called the tuple
(V, M, u)
undirected graph with vertex set (vertex set) V, edge set M and incidence mapping u.

7a shows a directed graph 700 and 7b shows an undirected graph 701 ,

Definition 2 (Scheduled Edges, initiated edges)

Let (V, E, g) be a directed graph and let v ε V. Then let E _term (v) be the set of v-terminated Kan th, ie e term (v): = {e ∈ E; G + (e) = v}, and E _init (v) the set of edges initiated by v, ie e init (v): = {e ∈ E; G - (e) = v}.

Definition 3 (way in one directed graph)

Be (V, E, g) is a directed graph, K ⊆ E.

(I)

als die Menge aller Wege von a nach b der Länge n mit Kanten K(Γ K / n(a, b) = {}, falls kein solcher Weg existiert).For a, b ε define V and n ε N

as the set of all paths from a to b of length n with edges K (Γ K / n (a, b) = {}, if no such path exists).

(Ii)

als die Menge aller Wege von a nach b mit Kanten aus K.For a, define b ε V.

as the set of all paths from a to b with edges from K.

Definition 4 (Judged Tree)

Let (V, E, g) be a directed graph, V ≠ 0. (V, E, g) is called directed tree, if there is a w ε V such that
| Γ _E (w, v) | = 1, for all v ε V \ {w}
and for all K ⊆ E, K ≠ E
| Γ _K (w, v) | = 0, for at least one v ε V \ <w>.

The is called there is exactly one way from w to every v ≠ w and the set of edges is not shrinkable. The unique corner w is called the root of the directed one Tree.

The second condition in the above definition 4 guarantees the uniqueness the root, which would otherwise not exist, and prevents the existence of "superfluous" edges in the tree.

8th shows an example of a directed tree 800 as part of the 7a sketched directed graph.

Lemma 5 (properties a directed tree)

Let (V, E, g) be a directed tree. Then, for all a, b ∈ V | Γ _E (a, b) | + | Γ _E (b, a) | ≤ 1.

Definition 6 (path length, throughput)

Be (V, E, g) is a directed tree with root w ε V. Define

(I)

For each v ε V \ {w}, let γ _E (v) ε Γ _E (w, v) be the unique path from w to v, ie Γ e (w, v) = {γ e (V)}

(Ii)

For every v ε V \ {w} there exists an n ε N {γ e (v)} = Γ e (w, v) = Γ n e (w, v)

Define | γ _E (v) | : = n as the path length of the path γ _E (v).

(Iii)

Define for | V | <∞ and all v ε V d e (v): = 1 + | {z ∈ V; Γ e (v, z) ≠ {}} | Ε N as the throughput of the node v.

Definition 7 (branch)

Let (V, E, g) be a directed tree. Define for all v ε V V e (v): = {v} ∪ {z ∈ V; Γ e (v, z) ≠ {}} as branch of the knot v.

It the following lemma applies:

Lemma 8 (power of the branch)

Let (V, E, g) be a directed tree and v ε V. Then we have d e (v) = | V e (V) |.

The overall network of the imaging system 300 including the portal processor is shown below as a graph. To model that existing connections between two nodes are always permeable in two directions, which symbolizes bidirectional communication, an undirected graph is first considered. To determine the routing, an equivalent directed graph is then derived.

Definition 9 (display graph)

• (i) 2 ≤ |V| < ∞,1 ≤ |M| < ∞,
• (ii) u injektiv (d. h. keine Zweiecke)
• (iii) u(E) ∩ {[x, x]; x ∊ V} = {} (d. h. schlingenfrei)
• (iv) w ∊ V sei ein ausgezeichneter Knoten und heiße Portal(knoten).

Let (V, M, u) be an undirected graph

• (I) 2 ≤ | V | <∞, 1 ≤ | M | <∞,
• (ii) u injective (ie no twigs)
• (Iii) u (E) ∩ {[x, x]; x ε V} = {} (ie loop-free)
• (iv) w ε V is an excellent node and hot portal (node).

Let (V, E, g) be the directed graph, for which holds: For every m ε M consider new elements m ^- and m ⁺ such that E: = {m - ; m ε M} ∪ {m + ; m ε M}, | E | = 2 | M |.

Choose the image g such that u (m) = {g (m - ), g (m + )}, for all m ε M.

• (v) Γ_E(w, v) ≠ {} für alle v ∊ V\{w} (d. h. zusammenhängend), so heiße (V, E, g) ein Anzeigeeinheits-Graph, im Weiteren auch bezeichnet als Display-Graph.

Applies additionally

• (v) Γ _E (w, v) ≠ {} for all v ε V \ {w} (ie connected), so hot (V, E, g) is a display unit graph, hereafter referred to as a display graph.

A corresponding undirected graph 900 (see. 9a ) and the equivalent directed pixel array graph 901 ( 9b ) are in the 9a and 9b exemplified.

• • Mit Ausnahme des Portal-Knotens 902 ist die Anzahl der Kanten, denen ein Knoten 903 als initiale (terminierende) Ecke angehören kann, durch eine Zahl q ∊ N beschränkt. Bislang wurden q = 4 (Orthogonales Netzwerk) und q = 6 (hexagonales Netzwerk) betrachtet.
• • Der gerichtete Graph 901 ist im Allgemeinen ein ebener Graph bzw. ein plättbarer Graph (es sind Erweiterungen denkbar, bei denen dies nur für den Sub-Graphen gilt, der den Portal-Knoten 902 nicht enthält, falls die Zuleitungen 904 nicht am Rand der Pixel-Anordnung 100 eingespeist werden).

According to this embodiment, a hexagonal 4 × 4 pixel field with a defect is selected. The above definition 9 is general. The considered networks have further limiting properties, which are mentioned here only briefly:

• • Except for the portal node 902 is the number of edges that a node has 903 can belong as an initial (terminating) corner, bounded by a number q ε N. So far, q = 4 (orthogonal network) and q = 6 (hexagonal network) have been considered.
• • The directed graph 901 is generally a planar graph or a planar graph (extensions are conceivable in which this applies only to the sub-graph representing the portal node 902 does not contain, if the supply lines 904 not on the edge of the pixel arrangement 100 be fed).

For further explanation, it makes sense next to the portal node 902 still those knots 903 to mark out a direct connection to the portal node 902 exhibit. As described above, these nodes become initiating nodes 903 that is, they represent the reference positions to which the launch pixel processors are assigned to the pixel array. The edges of the portal node 902 to the introduction nodes 903 will be referred to as supply lines 904 and the edges 905 between pixel processors referred to as network connections.

Definition 10 (supply lines, Network connections, introduction nodes)

Let (V, E, g) be a display graph with portal node w. The quantity of supply lines is then defined by e port : = {e ∈ E; G - (e) = w} and the amount of network connections e net : = {e ∈ E; G - (e) ≠ w ∧ g + (e) ≠ w}.

The set of initiation nodes is defined by V port : = g + (e port )

in the Further, the problem is considered that each node of a pixel array graph from the portal node within a Timeframe (within a refresh rate) transmitted an electronic message shall be.

happens this, as suggested by this problem, on chosen paths and paths that have separated do not intersect again, so this means that a directed tree is the sub-graph of the pixel array graph chosen shall be. This directed graph, also called a routing tree, then clearly defines the ways of the flow of information, not but the dynamics of the flow of information.

Of the Routing tree is not unique; in general, the amount is all potential Trees unmanageable large.

Definition 11 (Allowed tree quantity, allowed Edge set)

Let (V, E, g) be a display graph with portal node w ε V. The set of all allowed directional trees in (V, E, g) is defined as
B: = {(V, K, g | _K ); with K ⊆ E and (V, K, g | _K ) a directed tree with root w}.

The set of all allowable edge sets with respect to (V, E, g) is then defined as κ: = {K ⊆ E; (V, K, g | K ) Ε B}.

An exemplary legal tree 1000 is in 10 represented with the corresponding routing paths with the portal node 1001 as the root node of the directed tree 1000 ,

Based Definition 10 introduces the following terms:

Definition 12 (supply lines, Network Connections)

Let (V, E, g) be a display graph with portal node w and let K ε κ. The quantity of supply lines in K is then defined by K port : = E port ∩ K.

The amount of network connections through K net : = E net ∩ K.

to Rating of trees Below are a number of criteria listed below:

Definition 13 (Tree Ratings)

Be (V, E, g) a display graph with portal node w ε V and the amount κ of permissible Edge sets.

(I)

den Abstand des Knotens v von der Wurzel w im Display-Graphen.For all v ε V \ {w} defines

the distance of the node v from the root w in the display graph.

(Ii)

den Maximalabstand im durch K festgelegten Baum (V, K, g|_K).Defined for all K ε κ

the maximum distance in the tree defined by K (V, K, g | _K ).

is then the maximum distance in the display graph.

(Iii)

den Maximaldurchsatz im durch K festgelegten Baum (V, K, g|_K).

ist dann der Maximaldurchsatz im Display-Graphen.Defined for all K ε κ

the maximum throughput in the tree defined by K (V, K, g | _K ).

is then the maximum throughput in the display graph.

to Selection of the "best" trees or Edge sets are at least the following problems viewable:

(I)

Amount of trees whose nodes each have minimum distance to the root: O 1 : = {K ε κ; | γ K (V) | = l min (v) for all v ε V \ {w}},

(Ii)

Amount of trees whose maximum distance is minimal: O 2 : = {K ε κ; L (K) = L min }

(Iii)

Amount of trees whose maximum throughput is minimal: O 3 : = {K ε κ; D (K) = D min }

It is easy to see that O ₁ ⊂ O ₂ .

If O ₂ ∩ O ₃ ≠ {}, then all trees from O ₂ ∩ O _{3 are} minimizers of the functions L and K and are particularly suitable as routing tree.

If O ₂ ∩ O ₃ ≠ {} does not apply, then relaxed problems are necessary.

(Iv)

Amount of trees whose maximum distance is at most greater than minimum by a ε N ₀ : O a 4 : = {K ε κ; L (K) ≤ L min + a}

(V)

Quantity of trees whose maximum throughput is at most b ε N ₀ greater than minimal: O b 5 : = {K ε κ; D (K) ≤ D min + b}.

For a suitable choice of a, b ε N ₀ , O a / 4 ∩ O b / 5 ≠ {} will always be possible.

The Problem leaves but also as a multi-criteria combinatorial optimization problem to understand two objective functions.

For the display unit graph according to 9b is the routing tree 1000 according to 10 certainly not optimal and indeed not after any of the above criteria. The tree 1100 according to 11 in contrast, is even in O ₁ cut with O ₃ .

Above was explained like the ways of information flow in the display unit network by selecting a routing tree from a permissible Tree quantity can be set. Around the display unit nodes with the information needed to build up the image to supply one node to each node starting from the portal node transmitted electronic message along these paths. A parallel transmission of all electronic messages is generally not possible because certain capacities, how many messages are transmitted over an edge in a time cycle can be and how many messages are cached in a node can (Queue), not exceeded be allowed to. A temporal sequence (dynamics) of the information flow should therefore be determined.

Let (V, E, g) be a display unit graph with gantry node w. Let r: = | V | - 1 and V = {v ₀ , v ₁ , ... v _r }, v ₀ = w. If, in addition, K ε κ is given, certain "total" routing matrices τ and then certain "single" routing matrices σ ^l , l = 1, ..., r, can be introduced.

In τ, the information will be included how many electronic messages are to be transmitted over the individual edges of K in the individual clocks. In this case, conditions are formulated on τ such that the capacities are maintained and at the end an electronic message is present in each node. Between different messages (ie the single pixel data) is not yet distinguished in τ. How a specific single pixel data can be routed to the respective target pixel can not be seen directly from τ. However, it is possible to derive from τ certain "single" routing matrices σ ^l , l = 1, ..., r, which describe exactly this routing of the single pixel data to the destination pixels v _l , l = 1, ... r , The "single" routing matrices σ ^l , l = 1, ... r, are not necessarily unique, but the evaluation of the routing based on the routing duration will depend essentially only on τ. In the following, therefore, a routing is considered already given by τ.

Definition 14 (routing map, Routing matrix)

mit folgenden Eigenschaften

• (i) τij ≤ cport für alle j ∊ {1, ..., r} mit kj ∊ Kport und alle i ∊ {1, ..., n}, sowie τij ≤ cnet für alle j ∊ {1, ..., r} mit kj ∊ Knet und alle i ∊ {1, ..., n},
• (ii) für alle v ∊ V\{w} und 1 ≤ m ≤ n gilt
  
• (iii) für alle v ∊ V\{w} und 1 ≤ m ≤ n gilt
  
• (iv) für alle v ∊ V\{w} gilt
  
  c_port heißt Kapazität der Zuleitungen, c_net heißt Kapazität der Netzwerkverbindungen und q heißt maximale Queue-Länge. |τ| := nheißt Routing-Dauer. Die Menge aller (c_port, c_net, q)-Routing-Matrizen über (V, K, g|_K) werde mit
  
  bezeichnet.

Let K = {k ₁ , ..., k _r } ε κ (note: | K | = | V | - 1). Let c _port , c _net , q ∈ N. A (c _port , c _net , q) routing map or matrix over the tree determined by K (V, K, g | _K ) is a matrix

with the following properties

• (I) τ ij ≤ c port for all j ε {1, ..., r} with k j Ε K port and all i ε {1, ..., n}, as well as τ ij ≤ c net for all j ε {1, ..., r} with k j Ε K net and all i ε {1, ..., n},
• (ii) holds for all v ε V \ {w} and 1 ≤ m ≤ n
  
• (iii) holds for all v ε V \ {w} and 1 ≤ m ≤ n
  
• (iv) holds for all v ε V \ {w}
  
  c _port is the capacity of the supply lines, c _net is the capacity of the network connections and q is called the maximum queue length. τ | | : = n is called routing duration. The set of all (c _port , c _net , q) routing matrices over (V, K, g | _K ) will go with
  
  designated.

The Extension opposite consists of the previously considered routing trees primarily in that in τ additionally one temporal component is included.

The matrix entry τ _ij , i ∈ {1, ... n} j ε {1, ... r} means that messages are transmitted via the edge k _j in the i th time clock τ _ij .

condition (i) guaranteed compliance with specified supply capacities and Network capacity.

condition (ii) provides for the necessary causality in the web. Messages can only forwarded from a node if they were previously (this means at least one time clock earlier) transmitted to this node were.

condition (iii) taken into account Space limitations in the knot.

To Condition (iv) finally there is exactly one message in the node after n time units.

The Routing matrix thus provides a routing method together with the routing tree indicating the time sequence of each step, the the network is supplied with messages at the same time.

It is defined:

Definition 15 (routing)

. Die Menge aller Routings werde mit

bezeichnet.Let c _port , c _net , q ∈ N. A (c _port , c _net , q) routing is a tuple (K, τ) consisting of an allowable edge length K = {k 1 , ..., k r } Ε κ and a routing matrix τ ε

, The amount of all routings will go along

designated.

As Now the dynamic routing results for every single node, see below.

Determine matrices σ ^l ε {0,1} ^{n , r} , l = 1, ... r according to the following algorithm:

It is easy to show that the algorithm is well-defined and that τ ^r = 0 ⁿ ' ^r . Consequently, it is

für alle für alle l, l ~ ∊ {1, ..., r}. Ein Matrixeintrag σ l / ij = 1 besagt, dass die Nachricht an v_l im i-ten Zeittakt über die Kante k_j weitergeleitet wird.It is

for all for all l, l ~ ε {1, ..., r}. A matrix entry σ l / ij = 1 indicates that the message is forwarded to v _l in the ith time clock via the edge k _j .

When Proof sketch of the above well-definedness of the algorithm listed two lemmas:

Lemma 16 (well-definedness of σ ^l )

Let l ε {1, ..., r}. If τ ^l-1 ε N n, r / 0 satisfies condition (ii) from Definition 14 for all v ε V \ {w} and condition (iv) from Definition 14 for v: = e _l , then σ ^l can be computed choose the algorithm.

Lemma 17 (properties of τ ^l )

Let l ε {1, ..., r}. If τ ^l-1 ε N n, r / 0 satisfies the requirements of Lemma 16 and σ ^{l is} chosen according to the above algorithm, then τ ^l satisfies the requirements of Lemma 16.

Definition 18 (routing matrix to single node)

und es seien die Matrizen σ^l, l = 1, ..., r, gemäß obigen Algorithmus gewählt. Dann heißen die σ^l, l = 1, ..., r, Routing-Matrizen zu den Knoten v_l, l = 1, ..., r bzgl. (K, τ).Let c _port , c _net , q. Let (K, τ) ε

and let matrices σ ^l , l = 1, ..., r, be chosen according to the above algorithm. Then the σ ^l , l = 1, ..., r, are called routing matrices to the nodes v _l , l = 1, ..., r with respect to (K, τ).

Often we reverse the construction of the matrices τ and σ ^l , l = 1, ..., r. We specify matrices σ ^l , l = 1, ..., r by specifying the timing at which the message is forwarded to v _l via the path γ _K (v _l ). τ then turns out

The time sequence of the routing to each individual node and thus the σ ^l , l = 1, ..., r, are to be chosen so that the capacities of edges and nodes are not exceeded, ie that τ the points (i) and (iii) from Definition 14.

in the Furthermore, criteria become a "favorable" and, if possible, "optimal" selection of routing methods specified in a display unit graph. It becomes a routing hereinafter referred to as optimal, if it is the shortest possible duration claimed. To put this into mathematical language, be introduced the following terms.

Let (V, E, g) always be a display unit graph and, as before, let V = {v ₀ , ... V _r } be v ₀ = w.

Definition 19 (Minimum Routing duration)

(I)

die minimale Routing-Dauer über den durch K festgelegten Baum (V, K, g|_K).Let K = {k ₁ , ... k _r } ε κ and let c _port , c _net , q ∈ N. Then define

the minimum routing duration over the tree defined by K (V, K, g | _K ).

(Ii)

die minimale Routing-Dauer im Display-Graphen.Let c _port , c _net , q ∈ N. Then define

the minimum routing duration in the display graph.

Definition 20 (Optimal routing)

(I)

Let K = {k ₁ , ... k _r } ε κ and let c _port , c _net , q ∈ N. Under an optimal routing matrix in the tree defined by K (V, K, g | _K ) becomes a routing Matrix understood from the following quantity

(Ii)

Let c _port , c _net , q ∈ N. An optimal routing is understood as routing from the following set

The choice of an optimal routing matrix with an already defined routing tree as defined in Definition 20 (i) is simple. It is explained in this section for the special cases c _port and c _net = 1 and c _port and c _net > 1.

The solution of the optimization problem given in Definition 20 (ii) for free Choice of the routing tree is considerably more difficult. To be exact to solve, the problem is usually too complex. The following are from this Basic heuristic method explained for its solution. The solution of Optimization problem from definition 20 (i) with fixed routing tree provides important strategies for the favorable choice of the routing tree.

First, the special case is explained, in which c _port = c _net = 1.

Let q ε N be arbitrary and K ε κ. Without limiting the general validity, K _port = E _port (otherwise do not consider V _port \ g ⁺ (K _port ) as the introductory node, so set V _port : = g ⁺ (K _port )).

Because of c _port = 1, it is easy to think that

There is even equality. Be there

The idea of the following routing is that an electronic message arrives in the initiation nodes via each supply line at each time clock and is forwarded step by step to its respective destination node, that is to say the destination pixel processor, in the following time intervals. First, the messages are sent to the more distant nodes, later the messages are sent to the nodes that are close to the portal node, that is to say the pixel processor. An appropriate routing is in the 12a to 12i for the case c _port = c _net = 1 shown. Each of the small squares is an electronic message 1201 symbolizes which via the portal node 1202 to the preamble pixel processors 1203 in the pixel arrangement 100 to be led.

mit

= u derart angeordnet, dass

für i > j. Dies ist insbesondere dann erfüllt, wenn

für i > j. Sei nun l ∊ {1, ..., d} beliebig und sei

,der Weg von w nach

.Consider u ∈ V _port and set d: = d _K (u) = | V _K (u) |. It was

With

= u arranged such that

for i> j. This is especially true when

for i> j. Let l ε {1, ..., d} be arbitrary and let

, the way from w to

,

Then set for all i ε {1, ..., n} and j ε {1, ... r}

eine Routing-Matrix zu

definiert, genügt es zu zeigen, dass z + (d – l) ≤ n,denn dann reichen die n Zeittakte, um die Nachricht gemäß unserer Konstruktion von

an ihr Ziel

zu leiten. Wegen (1) ist l ≥ z und damit z + (d – l) ≤ d ≤ nund damit ist es gezeigt.To show that

a routing matrix too

defined, it suffices to show that z + (d-1) ≤ n, because then the n clocks suffice to deliver the message according to our construction of

to her destination

to lead. Because of (1), l ≥ z and so on z + (d-1) ≤d≤n and with that it is shown.

In accordance with the above considerations, the σ ^l can finally be determined for all l ε {1, ..., r} by considering all the introduction nodes. As usual, it is formed

It is easy to see that τ then really defines a (1,1, q) -ride over (V, K, g | K) for any q ε N and is optimal according to the above considerations. So it applies

12a shows the initial state to which all messages 1201 in the portal node 1202 are stored. After a first time clock, the first two messages 1201 the preamble pixel processors 1203 that is, the pixel processors of the pixel array 100 , via which the information about the pixel arrangement can be supplied to the respective pixel processors, fed and buffered there (see. 12b ). After another time step (cf. 12c ) the first two messages are already at first inner nodes 1204 the pixel arrangement and transmit two more messages 1201 are the introductory pixel processors 1203 been fed. After each further time step is the respective electronic message 1201 have been transmitted to each one pixel processor and there are two new messages 1201 in the pixel arrangement 100 in other words, the preamble pixel processors 1203 fed. The 12d . 12e . 12f . 12g . 12h . 12i show the successive progress of the transmission of the messages up to their respective destination pixel processor after every one clock cycle.

As a possible advantageous strategy for choosing an optimal routing with free choice of the routing tree as defined by Definition 20 (ii), it can be stated:
Select the routing tree in such a way that all initiation nodes have as large as possible (or, to be more precise, at most a value of 1) throughput and set the routing matrix according to the above considerations.

In the following, the second special case is briefly explained, in which: c: = c port = c net > 1, q ≥ c.

Let K ε κ. Without limitation of generality again K _port = E _port .

In this case, it is more difficult to specify the minimum routing time in advance. Thus, a routing matrix is developed which defines an optimal (c _port , c _net , q) routing over (V, K, g | K). From it, finally, the minimum routing duration can be determined. The idea for this variant of the routing is the same for the case c _port = c _net = 1 previously developed, except that in this case always c = c _port = c _net messages are simultaneously introduced into an initiation node to from there to be forwarded to the furthest, not yet notified nodes. Such routing is again in the 13a to 13f outlined.

It's first

mit

= u so angeordnet, dass

falls i > j. Sei l ∊ {1, ..., d} und

, d. h. die nächst kleinere ganze Zahl zu

. Sei (

, ...,

) der Weg von w nach

. Setze nun für alle i ∊ {1, ..., n ~} und j ∊ {1, ..., r}

Let u ∈ V _port and let d: = d _K (u) = | V _K (u) |. It was

With

= u arranged so that

if i> j. Let l ε {1, ..., d} and

ie the next smaller integer

, Be (

, ...,

) the way from w to

, Now for all i ε {1, ..., n ~} and j ε {1, ..., r}

As before, determine in the way σ ~ ^l for all l ε {1, ..., r} and set

Now delete all those lines in τ ~ that are equal to 0, ie set n: = min {n ~ ε N; τ ij = 0 for all n ~ <i ≤ n ~ and j = 1, ..., r} and

und L(K) ≤ n. It can be shown that τ defines an optimal (c _port , c _net , q) routing over (V, K, g | K) for any q ≥ c. Furthermore, applies

and L (K) ≤n.

How big n is actually depends on the concrete structure of the branches of the introduction nodes, but it can easily be calculated. For this purpose, the number of clock cycles n _u that is required to route all messages to the nodes of the branch of u is first calculated for each u ε V _port . V _K (u) and d are as above. Then:

from that results in the routing duration n as

herankommt. Setze die Routing-Matrix entsprechend obigen Überlegungen.As an alternative strategy for the choice of an optimal routing with free choice of the routing tree as defined in Definition 20 (ii) follows:
Select the routing tree so that all initiation nodes have the same throughput as possible and the tree in the branches of the initiation nodes is "sufficiently branched", so that n is as close as possible to

zoom comes. Set the routing matrix according to the above considerations.

A "sufficiently wide Branching "lies vividly then, if for all initiation nodes: Consider the branch of the introductory node, arrange the associated ones Knots according to ascending path length. Then should be the path lengths the node only increases all c nodes by the value 1, ie c nodes the path length 2, c knot the path length 3, ....

With low capacities of the respective nodes and the supply lines it is more important to equal one In this case, usually the throughput through the initiation nodes is the deciding factor for limiting the routing duration down. In this case, the introductory nodes are, so to speak, a bottleneck of the tree. At higher capacities, however, it is more important to pay attention to a sufficient number of branchings in the tree and thus short path lengths. Here it is usually the path lengths that limit the routing duration down. On the other hand, very high capacities are no longer useful since the hexagonal network limits the number of branches and certain minimum path lengths are predetermined by the topology of the network, that is to say the topology of the meshing or coupling of the pixel processors in the processor arrangement.

in the Further embodiments become the method for self - organization of the pixel processors in the Pixel arrangement explained.

• • Der zentralen externen Einheit, das heißt dem Portalprozessor ist die Topologie des Netzwerkes, das heißt die Anordnung der Pixelprozessoren in der Prozessor-Anordnung unbekannt.
• • Die Pixelprozessoren sind durch bidirektionale Verbindungen miteinander vermascht.
• • Eine direkte Kommunikation erfolgt nur zwischen jeweils einander unmittelbar benachbarten Nachbar-Pixelprozessoren.
• • Basis der Kommunikation ist der Austausch von elektronischen Nachrichten, wie sie beispielsweise in 14 dargestellt sind.
• • Jeder Kontakt mit anderen Komponenten zur Selbstorganisation (Positionsbestimmung, Erstellung von Routing-Tabellen etc.) und zum Bildaufbau wird durch verschiedene Nachrichten abgewickelt. 14 zeigt einen ersten Pixelprozessor 1401 mit hexagonaler Form sowie einen zweiten Pixelprozessor 1402, ebenfalls in hexagonaler Form. Der erste Pixelprozessor 1401 weist sechs bidirektionale Kommunikationsschnittstellen 1403 auf, was durch jeweils einen Doppelpfeil in 14 angedeutet ist. Auch die zweite Prozessoreinheit 1402 weist sechs bidirektionale Kommunikationsschnittstellen 1404 auf. Die erste Prozessoreinheit 1401 und die zweite Prozessoreinheit 1402 sind über eine Zuleitung 1405, das heißt eine elektrisch leitende Verbindung, welche selbstverständlich auch als optische Kommunikationsverbindung ausgestaltet sein kann oder als Funkverbindung miteinander derart gekoppelt, dass sowohl eine erste Nachricht 1406 von der ersten Prozessoreinheit 1401 zu der zweiten Prozessoreinheit 1402 übermittelt werden kann als auch eine zweite Nachricht 1407 von der zweiten Prozessoreinheit 1402 zu der ersten Prozessoreinheit 1401.

According to the embodiments, the following situation is assumed:

• The central external unit, that is, the portal processor, is the topology of the network, that is, the arrangement of the pixel processors in the processor array unknown.
• • The pixel processors are meshed together by bidirectional connections.
• • Direct communication takes place only between mutually immediately neighboring pixel processors.
• • Communication is based on the exchange of electronic messages, such as those in 14 are shown.
• • Each contact with other components for self-organization (positioning, creation of routing tables, etc.) and image composition is handled by various messages. 14 shows a first pixel processor 1401 with hexagonal shape as well as a second pixel processor 1402 , also in hexagonal form. The first pixel processor 1401 has six bidirectional communication interfaces 1403 on top of what is indicated by a double arrow in each case 14 is indicated. Also the second processor unit 1402 has six bidirectional communication interfaces 1404 on. The first processor unit 1401 and the second processor unit 1402 are via a supply line 1405 , that is, an electrically conductive connection, which of course can also be configured as an optical communication connection or as a radio link coupled together such that both a first message 1406 from the first processor unit 1401 to the second processor unit 1402 can be transmitted as well as a second message 1407 from the second processor unit 1402 to the first processor unit 1401 ,

According to the present embodiments, all the pixel processors are in error-free state 1401 . 1402 meshed with each other via the corresponding supply lines and the bidirectional communication interfaces.

The above problem is solved by self-organization based on local message exchange between two immediately adjacent processor units 1401 . 1402 solved.

The Self-organization method thus consists of distributed uniforms Algorithms that transmit these electronic messages Transfer communication interfaces.

As the process progresses, the processor units learn 1401 . 1402 their orientation and their level position within the processor array and the distance of the respective processor unit to the portal processor, generally to a reference position. The reference position may also be the position of a processor unit located at the point of initiation of the pixel array. In further steps, local routing paths between the individual processor units and the portal processor are embossed. The algorithms for selecting the routing paths are designed in such a way that, with a uniform information flow, the routing duration becomes as minimal as possible. The self-assembly also defines the algorithm for distributing the information when using the pixel arrangement as part of the image construction, that is, in the context of the representation of a digitized image on the pixel array. Due to the special design of the method, the shape of the pixel arrangement and thus also failed individual components play no role, so that according to the invention a high degree of fault tolerance is achieved.

• • Uniforme Teilalgorithmen zur Nachrichtenverarbeitung, die von den Pixelprozessoren ausgeführt werden,
• • dem Steueralgorithmus des Portalprozessors,
• • einem Nachrichtenkatalog, welcher die Schnittstelle der Teilalgorithmen darstellt.

The entire process comprises a combination of the following partial procedures:

• Uniform message processing algorithms executed by the pixel processors
• The control algorithm of the portal processor,
• • a message catalog, which represents the interface of the subalgorithms.

The following is a hexagonal meshing of the pixel processors within the pixel array 100 accepted without restriction of generality.

The transfer algorithms on orthogonal case or other plane meshes but is perfect according to the invention analogous to this representation given below.

According to one Communication layer model below the functions required according to the invention lying functions, such as ping messages, the backup the transmission using checksums, Acknowledgment of receipt, Re-request defective messages, etc. are not in the following considered. these can however, be readily implemented within the scope of the invention.

As a general rule applies in the process steps described below, that each pixel processor based on received messages for each its neighbor pixel processors creates a data set containing the information obtained in a stores memory associated with the respective processor.

In In a first part method, the pixel processors learn a uniform alignment.

There all connections of the portal processor according to the above convention with the Southwest side the corresponding launch pixel processors linked at the discharge points this can be used to create coherence.

To Measurement coherence messages are sent as parameters Number of connections containing the receive connection against clockwise from the east direction as defined above is.

Everyone Pixel processor is set as incoherent for initialization.

• 1. Falls die Prozessoreinheit 1500 schon kohärent ist, wird die Verarbeitung beendet.
• 2. Die Ost-Richtung wird anhand des Nachrichtenparameters bestimmt und alle Verbindungsbezeichnungen/Verbindungsnummerierungen werden entsprechend ausgerichtet.
• 3. Die Prozessoreinheit 1500 wird als kohärent gesetzt.
• 4. Über alle Verbindungen werden MessKoherenz-Nachrichten 1601, 1602, 1603,1604, 1605, 1606 von der Prozessoreinheit 1500 ausgesendet, deren Parameter jeweils so gewählt werden, dass die die jeweilige MessKoherenz-Nachricht 1601, 1602, 1603, 1604, 1605, 1606 empfangenden Prozessoreinheiten 103 sich auf obige Weise korrekt ausrichten können (vgl. 16).

When receiving a measurement coherency message 1501 (see. 15 ) from which the MessKoherenz message 1501 receiving processor unit 1500 the following steps are performed:

• 1. If the processor unit 1500 is already coherent, the processing is terminated.
• 2. The east direction is determined by the message parameter and all connection names / connection numbering are aligned accordingly.
• 3. The processor unit 1500 is set as coherent.
• 4. Across all links will be Measurement Coherence Messages 1601 . 1602 . 1603 . 1604 . 1605 . 1606 from the processor unit 1500 whose parameters are each selected so that the respective MessKoherenz message 1601 . 1602 . 1603 . 1604 . 1605 . 1606 receiving processor units 103 can correctly align in the above way (cf. 16 ).

The Part method for uniform alignment is set in motion by the portal processor over its Connect the Measurement Coherence message (2) with the parameter value 2 transmitted to the respective launch pixel processors. The part procedure terminates when the last processor unit has become coherent.

The Number of needed Timing to carry of the process corresponds to the maximum distance of a pixel processor from the portal processor. Until the "dying" of the last message communication may be one or two more timed cycles are needed.

In In another sub-method, the pixel processors determine by means of Exchange of electronic messages with each other automatically their local Position within the pixel array.

There the hexagonal field of the pixel processors within the pixel array each offset lines consists of the coordinate system according to this embodiment chosen so that the column numbers in the rows alternately even or are odd.

It It should be noted in this context that in the case of an orthogonal Construction of the pixel arrangement makes the coordinate system very simple canonical selectable is.

On the manner described above is enabled in the hexagonal field, that a processor is independent from the geometry of the pixel arrangement from its own position (i, j) with row i and column j the positions of its neighboring pixel processors can determine.

The respective positions are in 17 for the processor unit 1500 shown. How to get in 17 It is conventionally agreed that the column numbers increase from west to east (from left to right) and the line numbers increase from south to north (from bottom to top).

For position determination according to this embodiment MessPosition messages 1701 . 1702 . 1703 . 704 . 1705 . 1706 which contain two parameters, namely the line number and the column number containing the measurement position message 1701 . 1702 . 1703 . 1704 . 1705 . 1706 sending processor unit as her assumed position of the respective message 1701 . 1702 1703 . 1704 . 1705 . 1706 receiving processor unit has calculated.

to Initialization is the position of each pixel processor as (0,0) Are defined. The process of positioning begins at each Pixel processor as soon as it is coherent has become, as explained above has been.

All connections then become the MessPosition messages 1701 . 1702 . 1703 . 1704 . 1705 . 1706 shipped as in 17 shown.

• 1. Falls z > i, wobei i die eigene Zeilennummer darstellt, so wird i = z gesetzt.
• 2. Falls s > j, wobei j die eigene Spaltennummer darstellt, so wird j = s gesetzt.
• 3. Falls sich aufgrund von Schritt 1 oder Schritt 2 eine Änderung der eigenen Position (i, j) ergeben hat, so werden über alle Verbindungen MessPosition-Nachrichten 1701, 1702, 1703, 1704, 1705, 1706 versendet, wie in 17 dargestellt.

Upon receipt of a measurement position message 1701 . 1702 . 1703 . 1704 . 1705 . 1706 with row parameter z and column parameter s, the following steps are performed by the respective receiving processor unit:

• 1. If z> i, where i represents the own line number, then i = z is set.
• 2. If s> j, where j represents its own column number, then j = s is set.
• 3. If, due to step 1 or step 2, a change of the own position (i, j) has resulted, then MessPosition messages will be displayed for all connections 1701 . 1702 . 1703 . 1704 . 1705 . 1706 shipped as in 17 shown.

The Partial method is terminated when there are no position changes more results.

18 shows an example of the processor arrangement 1800 with different defects, which has automatically determined the positions of the individual processors according to the procedure described above. According to this embodiment, both failed, ie faulty processors and failed connections were used. This embodiment is also used in the course of this description in two variants with a different number of introduction processor units for the description of the other part-method.

The number of timing pulses required to perform the process is limited by the maximum distance of a pixel processor from another pixel processor in the processor array. Until the "dying" of the last message communication, one or two more clock cycles may be needed. Usually, however, the partial method is dependent on the geometry of the processor arrangement 1800 usually even faster.

In this context, it should be noted that in the representation of hexagonal pixel images or orthogonal pixel images from the portal processor, an image is applied to the thus determined coordinate system of the processor arrangement 1800 is carried out. In the case of the later part of the procedure established routing paths the portal processor now the locally stored information is transmitted, so that a corresponding mapping can be done in the portal processor.

In 18 is in the pixel array for each pixel processor, respectively 1801 the local position of the respective pixel processor 1801 within the processor arrangement 1800 applied in the form of a dome.

In an additional partial method, the distance of a processor unit from the portal processor, that is to say the length of the path from the pixel processor to the portal processor (see also definition 6), is generally the distance of a processor unit 1801 in the processor arrangement 1800 from a given reference position.

To initialize this sub-process is the distance of each processor unit 1801 defined as "infinite". According to this embodiment, the distance of each pixel processor to the portal processor is defined as a value greater than a maximum value that can be assumed to be the distance within the pixel array.

It will be without restriction of generality provided that the steps of the sub-procedure already presented above carried out were.

The process of distance determination is then performed by the portal processor by sending MessDistance (0) messages to the processor units at the initiation points of the processor array 1800 started.

• 1. Falls d ≥ a + 1, wobei d den eigenen Abstand darstellt, so wird d = a + 1 gesetzt.
• 2. Falls sich aufgrund von Schritt 1 eine Änderung des eigenen Abstandes d ergeben hat, so werden über alle Verbindungen MessDistance-Nachrichten 1901, 1902, 1903, 1904, 1905, 1906 an die jeweils benachbarten Prozessoreinheiten versendet (vgl. 19). Die jeweilige MessDistance-Nachricht 1901, 1902, 1903, 1904, 1905, 1906 enthält jeweils als Parameter den Abstandswert, den die Prozessoreinheit 1500 in dem vorangegangenen Schritt ermittelt hat.

Upon receipt of a measure distance message a, the following steps are performed by the respective processor unit receiving the measurement distance message:

• 1. If d ≥ a + 1, where d represents its own distance, then d = a + 1 is set.
• 2. If there has been a change in your own distance d due to step 1, MessDistance messages will be displayed for all connections 1901 . 1902 . 1903 . 1904 . 1905 . 1906 sent to the respective adjacent processor units (see. 19 ). The respective MessDistance message 1901 . 1902 . 1903 . 1904 . 1905 . 1906 Each contains as a parameter the distance value that the processor unit 1500 in the previous step.

The Part method terminates when there are no distance changes more results.

20 and 21 show the processor arrangement 1800 according to a first embodiment and a processor arrangement 2100 according to a second embodiment, wherein in the processor arrangement 1800 according to the first embodiment, all processor units 2001 in the bottom line 2002 the processor arrangement 1800 with the portal processor on their southwest side 2003 are coupled.

In the processor arrangement 2100 according to the second embodiment includes the bottom line 2101 the processor arrangement 2100 both processor units 2102 which are not coupled to the portal processor as well as processor units 2103 which via their located on the southwest side communication interfaces 2104 are coupled to the portal processor. According to the second embodiment, every third processing unit is in the bottom line 2101 Connected to the portal processor via its communications interface located on the southwest side.

The Number of needed Timing to carry of the process corresponds to the maximum distance of a processor unit from the portal processor. Again, until the "dying" of the last message communication one or two more timed cycles are needed.

In In this context, it should be noted that each processor unit due to each message received also the removal of its direct Adjacent processor units locally by the portal processor for later use can.

clear is used in this part-procedure in an iterative procedure of own distance value of the processor unit then changed, if the previously stored distance value is greater than that by a predetermined Value increased received distance value in each received message. In the case, that a processor unit changes its own distance value generated this one measurement distance message and sends it over all Communication interfaces to neighboring processor units, where the measurement distance message each contains its own distance as distance information or the distance value that the received processor unit receives from the portal processor preferably has a value increased by a predetermined value across from the own distance value, preferably a distance value which is around the Value "1" is increased.

in the Further, the partial procedure for regular backward organization will be described.

Around to carry out the following process steps, it is necessary that the distance of a pixel processor to a respective reference position has been determined and is thus known and preferably as respective distance information in the memory of the respective processor is stored.

In The partial method described below, the compounds between the respective processor units hereinafter referred to as channels Instances excellent.

The amounts of the processor units with the portal processor as the root node and the channels as edges between the respective processor units form a tree. This tree is used for the subsequent routing, as described above in connection with the graph theory basics has been written.

The channels be in regular Way so determined that each processor unit on a shortest path with the portal node is connected.

For initialization is every pixel processor 1500 defined as "disorganized." The process of organization is handled by the portal processor by sending MessOrganize messages 2201 . 2202 . 2203 . 2204 . 2205 . 2206 , which have no parameters, started across all connections.

• 1. Falls die Prozessoreinheit schon organisiert ist, wird die Verarbeitung beendet.
• 2. Über alle Verbindungen mit Ausnahme der Empfangsverbindung, das heißt der Verbindung, über die die MessOrganize-Nachricht 2201, 2202, 2203, 2204, 2205, 2206 empfangen worden ist, werden zusätzliche Mess-Organize-Nachrichten versendet (vgl. 22).
• 3. Die Prozessoreinheit ermittelt aufgrund der zuvor ermittelten Abstandsinformationen eine Nachbar-Prozessoreinheit, welche einen geringeren Abstand als sie selbst von der Referenzposition, vorzugsweise somit von dem Portalprozessor, aufweist. Es wird diejenige Nachbar-Prozessoreinheit ausgewählt und als "Vorgänger" definiert, welche als erste nach der gemäß 23 und 24 festgelegten Reihenfolge einen geringeren Abstand aufweist als die Prozessoreinheit selbst. Die Verbindung zwischen der Prozessoreinheit und ihrem "Vorgänger" wird besonders ausgezeichnet und "Kanal" genannt. Die Menge der Pixelprozessoren mit dem Portalprozessor als Knoten und den Kanälen als Kanten bilden dann einen Baum. Bei einem regulären Display ohne Fehler führt diese Vorgehensweise auf ein "Zickzack-Muster" bei der Festlegung der Kanäle.
• 4. Dem "Vorgänger" wird eine MessChannel-Nachricht geschickt und die Prozessoreinheit wird als organisiert gesetzt.

Upon receipt of a MessOrganize message 2201 . 2202 . 2203 . 2204 . 2205 . 2206 The processor units that receive the message receive the following steps:

• 1. If the processor unit is already organized, processing is terminated.
• 2. All connections except the receive connection, that is, the connection that the MessOrganize message uses 2201 . 2202 . 2203 . 2204 . 2205 . 2206 receive additional Mess Organize messages are sent (see. 22 ).
• 3. The processor unit determined on the basis of the previously determined distance information a neighboring processor unit, which has a smaller distance than they themselves from the reference position, preferably thus of the portal processor. The neighboring processor unit is selected and defined as a "predecessor", which is the first one according to 23 and 24 The connection between the processor unit and its "predecessor" is particularly excellent and called "channel". The set of pixel processors with the portal processor as nodes and the channels as edges then form a tree. For a regular display without errors, this procedure will result in a "zigzag pattern" when defining the channels.
• 4. A MessChannel message is sent to the "Predecessor" and the processor unit is set as organized.

at Receipt of a MessChannel message is from the the measurement channel message the receiving processor defines the sender as a "successor". Accordingly, then the connection between the processor unit and the "successor" a channel.

The Part method terminates after all processor units on this Have organized themselves.

25 shows an example of an organized processor unit 2500 , where the connections 2501 which channels are optically highlighted. About the channels 2501 When using the display, the pixel information, for example, thus the image information to be displayed, are routed.

26 and 27 show examples of the processor arrangement 1800 and 2100 after automatic organization as described above.

The Number of needed Timing to carry of the partial procedure to the backward Self-organization equals the maximum distance of a pixel processor from the portal processor. Until the "dying" of the last message communication can even in this case, one to two timed cycles are needed more.

The regular reverse organization leads error-free rectangular displays, ie display units, too good balanced trees.

Because all processor units are within the processor array 1800 . 2100 In the case of horizontal tears, this algorithm determines an element of the "optimal set" O ₁ defined above 2600 . 2700 as in the 26 and 27 However, the approach described above leads to the shaded portions of the processor arrangement 1800 . 2100 essentially be supplied by a single lead from the portal to the display.

Therefore will be additional in addition alternative options described the organization.

To the Setting up routing tables is the throughput of a pixel processor of considerable importance.

Of the Throughput is the number of pixel information needed to build each image is processed or passed on by that processor Need to become.

The mathematical definition of throughput is in Definition 6 above given.

These Number is identical to the number of pixel information over the Input channel are received.

To perform the following sub-process steps must be in the processor arrangement 1800 . 2100 a tree structure may have been organized by means of channels, for example, as described above.

The Partial method is sent by the portal processor by sending Mess Count Notes messages that have no parameters over all Connections to the respective introduction processor units started.

• 1. Über alle Ausgangs-Kanäle der die MessCountNodes-Nachricht empfangenden Prozessoreinheit werden wiederum MessCountNodes-Nachrichten 2802 versendet, wie in 28 dargestellt.
• 2. Alle Nachbar-Prozessoreinheiten, die über Ausgangs-Kanäle miteinander verbunden sind, werden mit einem Durchsatz mit dem Durchsatzwert "0" markiert.
• 3. Falls keine Ausgangs-Kanäle existieren, wird der eigene Durchsatz auf den Durchgangswert "1" gesetzt und es wird eine MessNodesSize-Nachricht 2901 über den Eingangs-Kanal an die jeweilige Vorgänger-Prozessoreinheit gesendet. 29 zeigt für eine Prozessoreinheit 1500 zwei eingehende MessNodesSize-Nachrichten, eine erste eingehende MessNodesSize-Nachricht 2901, welche den Wert d₁ enthält und eine zweite eingehende MessNodesSize-Nachricht 2902 mit dem Parameter d₂. Bei Empfang einer MessNodesSize-Nachricht mit Durchsatzparameter d ^ über einen Ausgangskanal werden von dem die MessNodesSize-Nachricht empfangenden Prozessoreinheit die folgenden Schritte durchgeführt: 1. Die Nachbar-Prozessoreinheit, von der die MessNodesSize-Nachricht 2901, 2902 empfangen wurde, wird mit dem Durchsatzparameter der MessNodesSize-Nachricht markiert. 2. Falls mindestens ein Ausgangs-Kanal mit einem Durchsatz mit dem Durchsatzwert „0" markiert ist, wird die Verarbeitung beendet. 3. Falls alle Ausgangs-Kanäle mit einem Durchsatzwert > 0 markiert sind, so wird der eigene Durchsatz d als Summe aller Ausgangs-Durchsätze +1 berechnet. 4. Es wird eine zusätzliche MessNodesSize-Nachricht 2903 von der Prozessoreinheit erzeugt und mit dem Durchsatzwert d, welche sich ergibt, gemäß folgender Vorschrift: d = d₁ + d₂ + 1 gemäß dem oben beschriebenen Ausführungsbeispiel, über den jeweiligen Eingangs-Kanal gesendet.

Upon receipt of an incoming MessCountNodes message 2801 The following steps are performed via the input channel by the processor unit receiving the MessCountNodes message:

• 1. All the output channels of the processor unit receiving the MessCountNodes message become MessCountNodes messages again 2802 shipped as in 28 shown.
• 2. All neighbor processor units, which are interconnected via output channels, are marked with a throughput with the throughput value "0".
• 3. If there are no output channels, the own throughput is set to the pass value "1" and it becomes a MessNodesSize message 2901 sent via the input channel to the respective predecessor processor unit. 29 shows for a processor unit 1500 two incoming MessNodesSize messages, a first incoming MessNodesSize message 2901 which contains the value d ₁ and a second incoming MessNodesSize message 2902 with the parameter d ₂ . Upon receipt of a MessNodesSize message with throughput parameter d 1 over an output channel, the processor unit receiving the MessNodesSize message performs the following steps: 1. The Neighbor processor unit from which the MessNodesSize message 2901 . 2902 is received is marked with the throughput parameter of the MessNodesSize message. 2. If at least one output channel is marked with a throughput with the throughput value "0", the processing is ended 3. If all the output channels are marked with a throughput> 0, the own throughput d becomes the sum of all the outputs - calculated throughputs +1 4. There will be an additional MessNodesSize message 2903 generated by the processor unit and having the throughput value d, which results, according to the following rule: d = d ₁ + d ₂ + 1 according to the embodiment described above, sent over the respective input channel.

The Part method terminates after the portal processor over all Connections received a MessNodesSize message.

The Number of needed Timing to carry of the partial procedure equals twice the maximum distance of a pixel processor from the portal processor. Until the "dying" of the last message communication can even in this case, one to two more bars are needed.

30 and 31 show examples of the processor arrangement 1800 respectively. 2100 after the throughputs have been determined automatically in the manner described above.

The respective throughput value is indicated in the respective pixel processors. These examples show that the throughputs of those injection processor units are very high, that of the respective horizontal crack 2600 . 2700 shaded area of the processor array 1800 respectively. 2100 have to provide.

Therefore, an alternative organization method will be described below which is even more flexible for errors, ie defects and irregular forms of a processor arrangement 1800 . 2100 , can react.

To achieve the most uniform throughput possible, there is a heuristic approach to the choice of a routing tree in the successive sending so-called MessToken messages, which in the processor arrangement 1800 . 2100 " Occupy seats ".

In analogy to a gradual coloring of the processor arrangement 1800 . 2100 By means of color streams, each discharge point is charged with tokens of a different "color". In this way, the processor arrangement 1800 . 2100 divided into color regions, which are each supplied via an initiation processor unit of the portal node.

Different expressed this means that one "color" or one individual mark for each of over one provided respective processor processing unit supplied processor unit is.

in the Further, the term "color" becomes more vivid Representation and accordingly marked with the same marker Area used as "color region".

• • Ein Tokengewicht bestimmt, um wie viel der Abstand zum Portal-Knoten maximal vergrößert werden darf aufgrund der Einfärbung.
• • Einmal gefärbte Pixel, das heißt Prozessoreinheiten, bleiben gefärbt, anders ausgedrückt bleiben markiert.
• • Die den Token versendende Prozessoreinheit wird zum „Vorgänger" und die Verbindung zu ihm zum Kanal. Im Weiteren nimmt das gefärbte Pixel, das heißt die markierte Prozessoreinheit, nur noch von dem jeweiligen Vorgänger Token an.
• • Token werden bevorzugt über Kanäle versendet.

The following heuristic strategies of distribution come into play:

• • A token weight determines how much the maximum distance to the portal node may be increased due to the coloration.
• • Once colored pixels, ie processor units, remain colored, in other words remain marked.
• The processor unit which transmits the token becomes the "predecessor" and the connection to it becomes the channel, furthermore the colored pixel, that is to say the marked processor unit, only accepts tokens from the respective predecessor.
• • Tokens are preferably sent via channels.

After completely coloring the processor assembly 1800 . 2100 is a reorganization within the colored areas required, because due to the partial process not optimal "meander channels" 3501 form, such as in 35 shown.

First, be in the following subsections the sub-procedures for processing the token allocation used messages described.

The Distance determination within a color region is as far as possible identical to the general distance determination described above to a reference position.

Of the Color distance determines the length the shortest Way of a processor unit to the portal processor, where all processor units of the path of the same color region.

to Initialization is the color difference of each processor unit as infinite defined and its color as undefined. According to this embodiment is the distance of each pixel processor to the portal processor as defines a value that is larger as a maximum value, within the pixel arrangement as a distance can be accepted. Likewise, the processor unit marks its Neighbor processor units as colored indefinitely with color difference infinite.

• 1. Die die MessColDistance-Nachricht versendende Prozessoreinheit wird mit der Farbe c und dem Farbabstand a markiert.
• 2. Falls die Farbe c nicht mit der eigenen Farbe f übereinstimmt, das heißt der Farbe f der die MessColDistance-Nachricht empfangenden Prozessoreinheit, so wird die Verarbeitung beendet.
• 3. Der eigene Farbabstand d wird als Minimum der Farbabstände von gleichfarbig markierten Nachbarn plus den Wert 1 gesetzt.
• 4. Falls sich aufgrund von Schritt 3 eine Änderung des eigenen Farbabstandes d ergeben hat, so werden über alle Verbindungen MessColDistance-Nachrichten 3201, 3202, 3203, 3204, 3205, 3206 mit den Parametern (f, d), das heißt anders ausgedrückt mit dem eigenen Farbabstand d und der eigenen Farbe f versendet (vgl. 32).

When receiving a MessColDistance message with color c and color space parameter a, the following steps are performed by the respective processor unit receiving the MessColDistance message:

• 1. The processor unit sending the MessColDistance message is marked with the color c and the color difference a.
• 2. If the color c does not match the own color f, that is, the color f of the processor unit receiving the MessColDistance message, the processing is ended.
• 3. The own color difference d is set as the minimum of the color distances of neighbors marked in the same color plus the value 1.
• 4. If, due to step 3, a change in the color spacing d has occurred, MessColDistance messages will be displayed for all connections 3201 . 3202 . 3203 . 3204 . 3205 . 3206 with the parameters (f, d), that is to say in other words with the own color difference d and the own color f (cf. 32 ).

To the Blocking neighbor processor units from received token messages According to the invention, MessBlockToken messages used, that is after receiving such a MessBlockToken message allowed no more tokens will be sent to these blocked neighbor processor units.

simultaneously Color and color spacing are the same as for the MessColDistance message communicated.

to Initialization are all neighboring processor units of a processor unit set as unblocked.

• 1. Die die MessBlockToken-Nachricht versendende Prozessoreinheit wird als blockiert gesetzt und mit der Farbe c und dem Farbabstand a markiert.
• 2. Falls die Farbe c nicht mit der eigenen Farbe f, das heißt der Farbe des die Mess-Block-Token-Nachricht empfangenden Prozessoreinheit übereinstimmt, wird die Verarbeitung mit dem weiter beschriebenen Schritt 5 fortgesetzt.
• 3. Der eigene Farbabstand d wird als Minimum der Farbabstände von gleichfarbig markierten Nachbar-Prozessoreinheiten plus dem Wert 1 gesetzt.
• 4. Falls sich aufgrund von Schritt 3 eine Änderung des eigenen Farbabstands d ergeben hat, so werden von der Prozessoreinheit MessColDistance-Nachrichten 3201, 3202, 3203, 3204, 3205, 3206 über alle Verbindungen mit Parametern (f, d) versendet, wie in 32 dargestellt.
• 5. Falls es einen Eingangs-Kanal gibt und alle Nachbar-Prozessoreinheiten als blockiert gesetzt sind, so wird eine MessBlockToken-Nachricht 3302 mit den Parametern (f, d) erzeugt und über den Eingangs-Kanal versendet, wie in 33 dargestellt.

Receiving an incoming MessBlockToken message 3301 with the color c and the color space parameter a as message parameters, the following steps are performed by the processor unit respectively receiving the MessBlockToken message:

• 1. The processor unit sending the MessBlockToken message is set as blocked and marked with the color c and the color difference a.
• 2. If the color c does not coincide with its own color f, that is, the color of the processor block receiving the measurement block token message, processing continues with step 5 described further.
• 3. The own color difference d is set as the minimum of the color distances of neighboring processor units marked in the same color plus the value 1.
• 4. If, due to step 3, a change of the own color difference d has resulted, the processor unit will send MessColDistance messages 3201 . 3202 . 3203 . 3204 . 3205 . 3206 sent over all connections with parameters (f, d), as in 32 shown.
• 5. If there is an input channel and all neighbor processor units are set as blocked, a MessBlockToken message will be issued 3302 generated with the parameters (f, d) and sent over the input channel, as in 33 shown.

For coloring, that is, for marking processor units and thus for defining color regions, that is to marked areas within the processor arrangement 1800 . 2100 According to the invention so-called MessToken messages are used.

at the processing of measurement token messages should be distinguished if the processor unit is still undyed or already from a token colored were.

• 1. Der potentielle eigene Farbabstand pd wird als Minimum der Farbabstände von mit der Farbe f gefärbten Nachbar-Prozessoreinheiten + 1 gesetzt.
• 2. Falls das Gewicht g ≤ pd – a ist, wobei a der Abstand (nicht der Farbabstand!) der Prozessoreinheit von dem Portalprozessor ist, so wird der die MessToken-Nachricht 3401 versendenden Prozessoreinheit eine MessBlock-Token-Nachricht geschickt und die Verarbeitung wird beendet (die Ausbreitung der Tokens wird daher durch einen relaxierten Abstand beschränkt).
• 3. Die die MessBlockToken-Nachricht 3401 sendende Prozessoreinheit wird als blockiert gesetzt. Die eigene Farbe wird als f gesetzt und der eigene Farbabstand als pd.
• 4. Der die Mess-Token-Nachricht 3401 sendenden Prozessoreinheit wird eine MessChannel-Nachricht geschickt und die Prozessoreinheit wird als organisiert gesetzt. Somit ist der Eingangs-Kanal festgelegt.
• 5. Über alle Verbindungen mit Ausnahme des Eingangs-Kanals der Prozessoreinheit 1500 werden MessBlockToken-Nachrichten 3402, 3403, 3404, 3405, 3406 versendet, wie in 34 dargestellt, um eine Tokenvergabe von dort zu verhindern.
• 6. Falls alle Nachbar-Prozessoreinheiten als blockiert gesetzt sind, so wird eine MessBlockToken-Nachricht 3402, 3403, 3404, 3405, 3406 über den Eingangs-Kanal gesendet, wie in 33 dargestellt.

Receiving an incoming MessToken message 3401 of weight g and color f as message parameters are received from an uncolored processor unit containing the measurement token message 3401 receives the following steps:

• 1. The potential own color difference pd is set as a minimum of the color distances of color-dyed neighbor processor units + 1.
• 2. If the weight is g ≤ pd-a, where a is the distance (not the color space!) Of the processor unit from the portal processor, then the MessToken message becomes 3401 The processor unit sends a MessBlock token message and processing is terminated (the propagation of the tokens is therefore limited by a relaxed distance).
• 3. The MessBlockToken message 3401 sending processor unit is set as blocked. The own color is set as f and the own color difference as pd.
• 4. The the measurement token message 3401 A MessChannel message is sent to the sending processor unit and the processor unit is set as organized. Thus, the input channel is fixed.
• 5. Over all connections except the input channel of the processor unit 1500 become MessBlockToken messages 3402 . 3403 . 3404 . 3405 . 3406 shipped as in 34 shown to prevent token assignment from there.
• 6. If all neighbor processor units are set as blocked, a MessBlockToken message will be generated 3402 . 3403 . 3404 . 3405 . 3406 sent over the input channel as in 33 shown.

at Receive a measurement token message with the weight g and the color f over the input channel, on the other hand, is from an already colored processor unit proceed differently.

• 1. Falls die empfangene Mess-Token-Nachricht nicht über den Eingangs-Kanal kam oder die Farbe f nicht mit der eigenen Farbe übereinstimmt, wird die Verarbeitung beendet.
• 2. Falls es nach der Reihenfolge R einen unblockierten Ausgangs-Kanal gibt, so wird über diesen Ausgangs-Kanal eine MessToken-Nachricht mit den Parametern (g, f) geschickt, das heißt, das Token wird weitergereicht, und die Verarbeitung wird beendet.
• 3. Falls es nach der Reihenfolge R eine unblockierte Verbindung gibt, so wird über diese Verbindung eine MessToken-Nachricht (g, f) versendet und die Verarbeitung wird beendet.
• 4. Über den Eingangs-Kanal wird eine MessBlockToken-Nachricht geschickt, da sich das Token nicht weiterreichen lässt.

For an even column number, consider an order R = (SE, SW, E, W, NE, NW), which corresponds to an order R of (southeast, southwest, east, west, northeast, northwest) and an odd column number one order R = (SW, SE, W, E, NW, NE), which corresponds to an order (southwest, southeast, west, east, northwest, northeast) and performs the following process steps:

• 1. If the received measurement token message did not come over the input channel or the color f does not match its own color, processing is terminated.
• 2. If there is an unblocked output channel after the order R, then a MessToken message with the parameters (g, f) is sent via this output channel, ie the token is passed on and the processing is terminated.
• 3. If there is an unblocked connection after the order R, a MessToken message (g, f) is sent over this connection and the processing is terminated.
• 4. A MessBlockToken message is sent over the input channel because the token does not know can be delivered.

Since in the choice of color regions, the channels can not be set optimally due to the partial method described above, as in 35 These channels are deleted with MessDeleteChannels messages and reset later. To terminate the partial procedure, the message is provided with a parameter "stamp" whose value is not identical to the correspondingly stored parameter in the processor unit. In this context, it should be noted that the portal processor uses a different "stamp" parameter each time it reorganizes.

• 1. Falls der eigene Stempelparameter identisch zu dem empfangenen Parameterwert "stamp" ist, wird die Verarbeitung beendet.
• 2. Der eigene Stempelparameter wird auf den Wert in der MessDeleteChannels-Nachricht "stamp" gesetzt.
• 3. Alle Kanäle werden gelöscht.
• 4. Über alle Verbindungen mit Ausnahme der Verbindung zu der die MessDeleteChannels-Nachricht sendenden Prozessoreinheit werden MessDeleteChannels-Nachrichten 3602, 3603, 3604, 3605, 3606 mit dem Parameter "stamp" gesendet, wie in 36 dargestellt.

Receiving an incoming MessDeleteChannels message 3601 the parameter "stamp" performs the following steps from the processor unit receiving the respective MessDeleteChannels message:

• 1. If the own stamp parameter is identical to the received parameter value "stamp", the processing is ended.
• 2. The own stamp parameter is set to the value in the MessDeleteChannels message "stamp".
• 3. All channels are deleted.
• 4. All connections except the connection to the processor unit sending the MessDeleteChannels message become MessDeleteChannels messages 3602 . 3603 . 3604 . 3605 . 3606 sent with the parameter "stamp", as in 36 shown.

To Clear the old channels become new channels set within a color region by using MessColOrganize messages.

The processing of incoming MessColOrganize messages 3701 and sending MessColOrganize messages 3702 . 3703 . 3704 . 3705 . 3706 is largely identical to the processing of MessOrganize messages as described above.

One The difference, however, is that the considered neighboring processor units identical to how the processing processor unit is colored have to and that not the distance, but the color difference as a criterion is used.

to execution of the sub-method described above should all in the pixel array described steps have been carried out until the distance determination as explained above be.

As above in the first embodiment the connections are specially designated as "channels".

In a first step, the portal processor sends a MessColDistance message for all connections 4001 (see. 40 ) with the parameters (f, 0) with different color parameters f. Thus, all neighbor processor units mark the portal processor with a different color.

On this way is guaranteed in each case an individual starting from each introduction processor unit and unique marking takes place.

In a second step, successive MessToken messages with the parameters (g, f) with identical weight g ε N ₀ and different color parameter f are sent by the portal processor over all connections to all processor units of the processor arrangement 1800 . 2100 to color.

The sub-method terminates when MessBlockToken messages have arrived over all connections of the pixel processor, that is, when the processor array 1800 . 2100 was completely colored.

It should be noted in this regard that the entire processor arrangement 1800 . 2100 can always be completely colored with this method.

38 shows the processor arrangement 2100 in the event that it was colored with the weight g = 4 and in which the throughput was represented by the organization. How to compare with 30 Seen through regular backward organization sees, the tree is significantly better balanced.

However, due to the construction of this partial process, meandering paths are formed within the colored areas 3801 so that the processor units are not connected to the portal processor by the shortest possible distance.

Therefore in a third step, the portal processor over all Connect a MessDeleteChannels message as explained above, around the formed channels to delete. Immediately after this message, all connections become one MessColOrganize message sent within the colored areas new channels forms, which then shortest Represent connections.

The Part method terminates after all processor units organized in this way. The number of required clocks to carry out The process corresponds to the maximum color difference of a pixel processor from the portal processor. Until the "dying" of the last message communication can even in this case, one to two more bars are needed.

Of the generated routing tree hangs from the weight g, which as a parameter in the respective measurement token message is included, from.

39 shows the processor arrangement 1800 for after reorganization with weight g = 4 and the corresponding meander paths 3901 ,

The weight g indicates how much the color difference of a processor unit may be greater than the distance itself. The larger the weight g, the better balanced will usually be the resulting tree, but the longer the paths in this tree are usually. For explanation is on 41 to indicate in which the processor arrangement 1800 after the formation of the meander paths with the weight g = 0 and on the 42 in which the processor arrangement 1800 are shown after the formation of the meander paths with the weight g = ∞.

The best choice of weight usually depends from the transport properties of the respective compounds, the is called how many messages are sent per time via a connection can be. The smaller this number is, the bigger is usually the best weight have to be.

before Two methods for selecting a routing tree have been described.

If a routing tree is selected was, that is if the corresponding channels were selected so can an optimal routing for This tree can be determined in a very simple way. The basics For this purpose, in the description of the graph theoretic Basics explained.

In a first step, all pixel processors, that is, the processor units within the processor arrangement 1800 . 2100 , numbered.

The Numbers will follow used as destination addresses during routing. In a second step will be the collected local information from the respective Processor units transmitted to the portal processor. In the portal processor will follow created the overall routing table.

According to this embodiment, MessNumbering messages are used to number all processor units in the pixel array 1800 . 2100 used. The prerequisite is that the throughput of the respective processor units has already been determined, for example according to the partial method described above.

The partial procedure of numbering is done by the portal processor by sending MessNumbering messages 4301 via the output channels of the portal processor, which are transmitted to the initiation processor units started.

If throughputs d ₁ , d ₂ , d ₃ ,... Have been determined for the corresponding neighboring processor units, the respective MessNumbering message becomes 4302 the parameter 1, 1 + d ₁ , 1 + d ₁ + d ₂ , ... transmitted as message parameters.

• 1. Die eigene Nummer der Prozessoreinheit wird auf den Wert n, die dem Wert der empfangenen MessNumbering-Nachricht 4301 entspricht, gesetzt.
• 2. Über alle Ausgangskanäle der Prozessoreinheit wird je eine von der Prozessoreinheit erzeugte zusätzliche MessNumbering-Nachricht 4302 erzeugt und mit den Parametern n + 1, n + d₁ + 1, n + d₁ + d₂ + 1, ... versendet, wobei d₁, d₂, ... die Durchsätze der entsprechenden Nachbar-Prozessoreinheiten sind.

After receiving a MessNumbering message 4301 with the parameter n via the respective input channel of the processor unit (cf. 43 ) are from the MessNumbering message 4301 receiving processor unit performed the following steps:

• 1. The processor unit's own number is set to the value n, which is the value of the received measurement numbering message 4301 corresponds, set.
• 2. Over each output channels of the processor unit is an additional MessNumbering message generated by the processor unit 4302 and sent with the parameters n + 1, n + d ₁ + 1, n + d ₁ + d ₂ + 1, ..., where d ₁ , d ₂ , ... are the throughputs of the corresponding neighboring processor units.

The Partial method terminates when the last processor passes through the last one Processor unit has been numbered. The number of required clocks to carry out of the partial procedure corresponds to the maximum distance of a processor unit via channels from the portal processor. Until the "dying" of the last message communication can also with this partial procedure still one or two timings more needed.

The 44 and 45 show the pixel arrangements 1800 ( 44 ) and 2100 ( 45 ) after numbering of the individual processor units within the respective pixel arrangement.

The Number of a processor unit can easily be used as the address for Routing of data or even images are used, as each output channel a processor unit assigned a unique number interval is. Each processor unit can thus be a simple routing table invest.

In the example of 45 For example, the table for the processor unit numbered 123 is the same as in the routing table 4600 in 46 is shown.

• • Die Position der jeweiligen Prozessoreinheit innerhalb der jeweiligen Pixelanordnung, das heißt die Zeile und die Spalte, in der sich die Prozessoreinheit befindet,
• • die Pixelnummer,
• • der Abstandswert, mit dem der Abstand der Prozessoreinheit von dem Portalprozessor angegeben wird,
• • der Farbabstand, und
• • der Durchsatz der Prozessoreinheit.

The locally generated information is communicated to the portal processor using MessCollectInfo messages containing the following message parameters:

• The position of the respective processor unit within the respective pixel arrangement, that is to say the row and the column in which the processor unit is located,
• • the pixel number,
• The distance value with which the distance of the processor unit is specified by the portal processor,
• • the color difference, and
• • the throughput of the processor unit.

The MessCollectInfo messages are from the processor units respectively sent as soon as the respective processor unit numbered has been.

With This information allows the pixel processor to use pixel images on the real pixel field (sampling) and on the other these Route image data using the pixel numbers.

At the Sending an entire image, that is, when supplying the data to all processor units, be doing the messages first, the longest way have, as described above in the description of graph theoretic Basics explained.

Out this routing table then also results directly in the routing duration, with the the routing trees be rated.

• • Die Nummer des Pixels, welches adressiert wird, und
• • die Farbinformation für dieses Pixel, beispielsweise Rot-Grün-Blau-Werte.

With the help of the pixel numbers and the previously described routing tables, a pixel image can be sent in a very simple manner during further operation of the display. For this, the portal processor sends messages of the type MessRGB which are provided with the following parameters:

• • The number of the pixel being addressed, and
• • the color information for this pixel, for example red-green-blue values.

47 shows an example of an image representation on the pixel array. Of course, the representation is independent of the selected routing tree.

before the selection and the evaluation of routing matrices has been described, this means essentially of routing ways. The evaluation criterion is included the routing duration has been. Because a real combinatorial optimization due to the complexity usually not feasible in a short time is an alternative was presented above.

Of the freely selectable Parameter is the weight g. This process can be used to (partially) optimize the routing duration from the portal processor also several times with different weights g performed become.

Usually will we consider and examine the weights g = 0, 1, 2, 3, ...

These have proven to be advantageous in numerical considerations. The routing which is the shortest Routing duration can then be finally used.

To perform the process multiple times, the portal processor uses the MessRetry message, which deletes all channels, color regions, and color spaces, as in 48 is shown. To terminate the process, the MessRetry message is tagged with the parameter "stamp", the value of which is not identical to the processor unit's stored parameter, in other words, the portal processor uses a different "stamp" parameter each time it is reset.

• 1. Falls der eigene Stempelparameter identisch zu dem in der MessRetry-Nachricht enthaltenem Stempelparameter „stamp" ist, wird die Verarbeitung beendet.
• 2. Der eigene Stempelparameter wird auf den Wert des in der MessRetry-Nachricht enthaltenen Stempelparameterwerts „stamp" gesetzt.
• 3. Alle Nummerierungen, Kanäle, Farbregionen, Farbabstände und Token-Blockierungen werden gelöscht.
• 4. Über alle Verbindungen mit Ausnahme der Verbindung zu der die MessRetry-Nachricht sendenden Prozessoreinheit werden zusätzliche MessRetry-Nachrichten 4802 übertragen, wie in 48 dargestellt ist.

Upon receipt of an incoming MessRetry message 4801 the parameter "stamp" will be followed by the MessRetry message 4801 received processor unit performed the following steps:

• 1. If the own stamp parameter is identical to the stamp parameter "stamp" contained in the MessRetry message, the processing is ended.
• 2. The own stamp parameter is set to the value of the stamp parameter value "stamp" contained in the MessRetry message.
• 3. All numbering, channels, color regions, color spaces, and token blocks are deleted.
• 4. All Messages except the connection to the processor unit sending the MessRetry message become additional MessRetry messages 4802 transferred as in 48 is shown.

During the Operation of the pixel arrangement can Due to wear and tear errors occur at the time of the above Self-organization did not exist yet. For self-recognition this error can more messages are used.

To The model assumption shown above may be from a local point of view Processors a mistake only exist in that a previously connected Neighbor processor is no longer available. He can not judge if only the connection to this neighbor processor or whether the neighbor processor itself has failed. In such a Occurrence but an error message, below as MessError message sent to the portal processor that identifies it itself, preferably using the own pixel number as a message parameter and the additional contains the number of the newly failed connection.

A possible Reaction of the portal processor to such a message is a global reset of the pixel array using a MessReset message.

When In response to this message, each pixel processor directs this message to all neighbor processors and deletes all data, which at the Organization were determined. To schedule this process Every pixel processor should observe a certain dead time whose end he does not respond to further messages. The dead time Prevents the spread of MessReset message infinite often repeated.

In summary, in 51 an overview of the messages used, their respective parameters listed.

It It should be noted in this context that the news catalog Of course functional to any additional News is expandable.

49 shows an additional embodiment of the invention, in which the processor units 4901 are arranged in a matrix-like manner in a first hierarchical level and are fully meshed with each other. The processors 4901 the pixel arrangement 4900 In this case, they have a quadrilateral, preferably a square, shape and are coupled with a group of pixels, that is to say pixels or sensor elements, in a controlling and reading manner.

According to this embodiment, each processor for controlling or reading is 4 × 4 pixels 4902 , which each become a pixel block 4903 are grouped, coupled.

The individual pixel group processors are in an orthogonal network with one another by local nearest neighbor connections, as illustrated above 4904 networked with each other.

Between every two processors 4901 For example, one or more connections can run in order to allow, for example, bidirectional data transmission or the separate distribution of the supply voltages. In the layer of pixels 4902 As explained above, the individual pixel elements are included, each pixel block 4903 be controlled by a conventional matrix drive, as for example in 50 is shown.

The matrix controller 5000 in 50 shows an example of a pixel block 5001 and a column addressing unit serving as a shift register 5002 is designed as well as a line addressing unit 5003 , which is also designed as a shift register. The data is about a data source 5004 the input of the shift register 5001 supplied to the column addressing unit and a clock generation unit 5005 , which on the output side with the input of the column addressing unit 5003 is coupled.

On this way, the vertical wiring effort between the both levels, the processor level and the pixel level are kept low, because only one serial data transfer over only a line performed in which the clock signals are also obtained from the data signal itself become.

It It should be noted in this regard that more than two levels that can be present is called Groups of pixel group processors can in turn be grouped together so that a deeper hierarchical tree structure results.

The Pixel group processors can it's like being orthogonal meshed in the picture but also other meshes, especially a hexagonal mesh as explained above as well possible.

The Pixel group processors can Furthermore, exchange your messages in any format. Preferably However, they exchange message blocks with each other that lead to Example address code may contain with the help of which the image information taken in data packets from Processor to processor led can be. That way you can even defects in the matrix are bypassed, resulting in a rigid x / y addressing via Row lines and column lines is not possible.

ever for efficiency of the pixel group processors this in addition to the information transfer and sharing information also take on other tasks, such as compression or decompression of image information.

The Architecture can also be for large-area sensor arrays, such as fingerprint sensors, touchpads or letter recognition sensors be used.

So For example, each pixel group processor may wait until an event, that is an input with a pen, etc. occurs in a pixel group and then send that data to the edge of each matrix, respectively route. In this way it can be avoided that always the whole sensor surface must be scanned by an external addressing unit. Clearly, this corresponds to a local triggering by an event in place of a global image analysis.

The Pixel group processors can for example, using a technique such as the fluidic Self Assembly, as described in [3], into a suitable carrier substrate be introduced, as according to the first embodiment described.

The Connections between the processors as well as the sensor or display matrices can then in further process steps on the carrier substrate with the processors be applied.

Preferably can the upper functional layers realized by printable circuits be as they are provided in the polymer electronics.

It It should be noted that the partial procedures described above all independently from each other, i. independent carried out can be. you need only the ones for the respective sub-procedure required input information. It is, however, basically irrelevant, in what way the required input information have been determined. Nevertheless, the significant advantages in the context of the interlocking and joint execution of several or all partial procedures to indicate, since in this case the inventive concept described above continuously is implemented.

• [1] T.J. Nelson und J.R. Wullert, Electronic Information Display Technologies, World Scientific, Kapitel 8.2, 1997
• [2] K. Amundson, Microencapsulated Electrophoretic Materials for Electronic Paper Displays, International Display Research Conference, 2000
• [3] J.S. Smith, High-Density, Low Parasitic Direct Integration by Fluidic Self-Assembly (FSA), IEDM, S. 201 – 204, 2000
• [4] JP 63240667 A
• [5] WO 01/90915 A2
• [6] H.Y. Youn und A.D. Singh, Near Optical Embedding of Binary Tree Architecture in VLSI, 8th International Conference on Distributed Computing Systems, S. 86 – 93, 1988

This document cites the following publications:

• [1] TJ Nelson and JR Wullert, Electronic Information Display Technologies, World Scientific, Chapter 8.2, 1997
• [2] K. Amundson, Microencapsulated Electrophoretic Materials for Electronic Paper Displays, International Display Research Conference, 2000
• [3] JS Smith, High Density, Low Parasitic Direct Integration by Fluidic Self-Assembly (FSA), IEDM, pp. 201-204, 2000
• [4] JP 63240667 A
• [5] WO 01/90915 A2
• [6] HY Youn and AD Singh, Near Optical Embedding of Binary Tree Architecture in VLSI, 8th International Conference on Distributed Computing Systems, pp. 86-93, 1988

100

Pixel arrangement

101

substratum

102

deepening

103

processor unit

300

Bildanzeigendes system

301

source

302

Display unit portal

303

Pixel arrangement

401

bidirectional Communication interfaces

402

electrical management

501

bidirectional Communication interfaces

502

electrical management

600

First alignment

601

Second alignment

603

third alignment

604

Fourth alignment

605

Fifth direction

606

Sixth alignment

700

directed graph

701

undirected graph

800

directed tree

900

undirected graph

901

directed Pixel arrangement graph

902

Portal node

903

node

904

supply

905

edge

1000

Permitted tree

1001

Portal node

1100

tree

1201

message

1202

Portal node

1203

Lead-pixel processors

1204

First inner knots

1401

first pixel processor

1402

second pixel processor

1403

bidirectional Communication interface first

pixel processor

1404

bidirectional Communication interface second

pixel processor

1405

supply

-1,406

First message

1407

Second message

1500

processor unit

1501

MessKoherenz message

1601

MessKoherenz message

1602

MessKoherenz message

1603

MessKoherenz message

1604

MessKoherenz message

1605

MessKoherenz message

1606

MessKoherenz message

1701

Measurement position message

1702

Measurement position message

1703

Measurement position message

1704

Measurement position message

1705

Measurement position message

1706

Measurement position message

1800

Processor arrangement

1801

pixel processor

1901

Measuring Distance message

1902

Measuring Distance message

1903

Measuring Distance message

1904

Measuring Distance message

1905

Measuring Distance message

1906

Measuring Distance message

2001

processor unit

2002

Lowest Line processor arrangement

2003

Southwest side processor unit

2100

Processor arrangement

2101

Lowest Line processor arrangement

2102

Processor units, which not with the portal processor

coupled are

2103

Processor units, which with the portal processor

coupled are

2201

MessOrganize message

2202

MessOrganize message

2203

MessOrganize message

2204

MessOrganize message

2205

MessOrganize message

2206

MessOrganize message

2600

Horizontal cracks

2700

Horizontal cracks

2801

incoming Measuring count nodes message

2802

sent Measuring count nodes message

2901

First incoming MessNodesSize message

2902

Second incoming MessNodesSize message

2903

sent Measurement nodes size message

3201

MessColDistance message

3202

MessColDistance message

3203

MessColDistance message

3204

MessColDistance message

3205

MessColDistance message

3206

MessColDistance message

3301

received Measurement block token message

3302

sent Measurement block token message

3401

incoming Measurement token message

3402

sent Measurement block token message

3403

sent Measurement block token message

3404

sent Measurement block token message

3405

sent Measurement block token message

3406

sent Measurement block token message

3601

incoming MessDeleteChannels message

3602

sent MessDeleteChannels message

3603

sent MessDeleteChannels message

3604

sent MessDeleteChannels message

3605

sent MessDeleteChannels message

3606

sent MessDeleteChannels message

3701

incoming MessColOrganize message

3702

sent MessColOrganize message

3703

sent MessColOrganize message

3704

sent MessColOrganize message

3705

sent MessColOrganize message

3706

sent MessColOrganize message

3801

Meandering path

3901

Meandering path

4301

incoming MessNumbering message

4302

sent MessNumbering message

4600

Routing table

4801

incoming MessRetry message

4802

sent MessRetry message

4900

Pixel arrangement

4901

processor unit

4902

pixel

4903

pixel block

5000

matrix control

5001

pixel block

5002

shift register

5003

Line addressing unit

5004

Data Source

5005

Clock generation unit

Claims (12)

A method for determining a spacing of processor units to at least one reference position in a processor arrangement with a plurality of processor units, each processor unit having one bidirectional communication interface with at least one coupled to the adjacent processor unit and messages exchanged between adjacent processor units, • in which a first message is generated by a first processor unit, wherein the first message includes first distance information, which the distance of the first processor unit or the distance of the one first message receiving second processor unit from the reference position contains • in which the first message from the first processor unit to the second Processor unit is sent, • dependent on the distance information of the distance of the second processor unit is determined or stored from the reference position, and • in which a second message is generated by the second processor unit, which contains a second distance information which the distance of second processor unit or the distance of a second message contains receiving third processor unit from the reference position, • in which the second message from the second processor unit to the third Processor unit is sent, • dependent on the second distance information is the distance of the third processor unit determined or stored from the reference position, • in which the process steps for all processor units are performed in the pixel array. The method of claim 1, wherein each processor unit is coupled with at least one pixel, so the pixel of the respective processor unit assigned to it is controllable. The method of claim 2, wherein at least one Part of the pixels is each configured as a sensor. The method of claim 2, wherein at least one Part of the pixels each designed as an imaging element is. Method according to one of claims 1 to 4, • in which the processor units each arranged in a hexagonal area are and • at Each processor unit has six adjacent processor units each having a bidirectional communication interface with the processor unit are coupled. Method according to one of claims 1 to 5, wherein the pixels have a hexagonal shape. Method according to one of claims 1 to 4, • in which the processor units are each arranged in a rectangular area, and • in which each processor unit has four adjacent processor units each, which are each coupled via a bidirectional communication interface with the processor unit. Method according to one of claims 1 to 4 or 7, in which the pixels have a rectangular shape. Method according to one of claims 1 to 8, wherein before determining the distance of the pixel processors from the reference position the local Positions of the processor units within the processor array can be determined by starting from a processor unit a point of initiation of the processor arrangement in each case position-finding messages, which at least one row parameter z and a column parameter s, which the line number or column number of the Message sending processor unit or the line number or Column number of the processor unit receiving the message within contains the processor arrangement, be transmitted to adjacent processor units and of the respective processor unit, the following steps are performed: • if the Line parameter in the received message is greater than the previously stored one Line number of the processor unit, then becomes the own line number the processor unit the line parameter value z of the received message associated • if the column parameter in the received message is larger as the own column number of the processor unit, it is stored Column number of the column parameter value of the received message associated • if your own line number and / or your own column number due to of the above-described method steps have been changed new position measurement messages with new line parameters and new ones Column parameters are generated, each containing the row number and column number the processor unit sending the message or the line number and column number of the processor unit receiving the message contains and these are about the bidirectional communication interfaces to a respective one Transfer neighboring processor unit. Method according to one of claims 1 to 9, • in which in an iterative method, the own distance value of the processor unit then changed becomes if the previously stored distance value is greater as the received distance value increased by a predetermined value in each received message, and • in which, in the event that a processor unit changed your own distance value, this one distance measurement message generated and over all communication interfaces to neighboring processor units sends, with the distance measurement message each contains its own distance as distance information or the distance value that the received processor unit receives from the portal processor having. The method of claim 10, wherein the distance value a value increased by a predetermined value against the own distance value has. Processor arrangement with a multiplicity of processor units, • each one Processor unit over a bidirectional communication interface with at least one coupled to adjacent processor unit and wherein for determining the respective distance of a processor unit of the processor arrangement from a reference position messages are exchanged between adjacent processor units, • where each message is one Contains distance information, which is the distance of a processor unit sending the message or the distance of a processor unit receiving the message from the reference position, and • where each processor unit is set up such that from the distance information of a received message the own distance to the reference position can be determined or stored.