Data processing system and multiprocessor system

Details Data processing system and multiprocessor system Data processing system and multiprocessor system

2001-04-19

2004-11-02

Treat, William M. (Department: 2183)

Electrical computers and digital processing systems: processing

Processing control

Processing control for data transfer

C711S001000, C711S100000, C711S147000, C345S506000

Reexamination Certificate

active

06813706

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a multiprocessor system that distributes sequentially received data among a plurality of parallel processors, and particularly to a multiprocessor system usable for graphic processing for generating and displaying computer graphics images on a display. More particularly, the present invention relates to a multiprocessor system usable for texture mapping so as to paste a pattern or texture (e.g. marble, bark, aluminum, etc.) on a surface of a three-dimensional object.
BACKGROUND ART
Applicable fields of commuters have been expanded along with technical innovations in recent years. One example of such fields is “computer graphics” for creating and processing graphics and images by a computer. Recently “three-dimensional graphics” that generates and displays a two-dimensional image of a three-dimensional object has come to be highlighted as computer display capability has been enhanced and graphic processing has been advanced. The three-dimensional graphics mentioned here represents by a mathematical model an optical phenomenon occurring, for example, when a three-dimensional object is illuminated by a light source, and generates an image by applying shading or gradation to the surface of the object based on the mathematical model, thereby displaying the object as a three-dimensional like image on a screen. Such a three-dimensional graphics technique has been used more and more in CAD/CAM in scientific, engineering, manufacturing and other application fields, and in various software development fields.
Generally, three-dimensional graphics processing includes two processes; “modeling” and “rendering”. “Modeling” is a process for inputting to a computer and editing data such as shape, color, and surface characteristics of a three-dimensional object (e.g. an aircraft, a building, a cat, etc.) to be rendered on a screen.
In other words, modeling is a process for fetching data associated with the object into a computer in a format usable for the subsequent rendering. There are several methods for the modeling, such as CSG (Constructive Solid Geometry), polygon, Bezier, metaball, etc.
“Rendering” is a process for generating an image according to what the object looks like when it is seen from a particular position. Specifically, it is a process for coloring and shading the surface of a three-dimensional object on the basis of three-dimensional data (e.g. a position of a light source relative to the object, highlight, shade, and color) created by a modeler. The rendering process is subdivided into the respective operations “coordinate conversion”, “hidden surface removal”, “shading”, and “measure for giving reality”. The “coordinate conversion” converts each coordinate value used to define a model to a coordinate value on a screen as seen from a viewpoint position. The “hidden surface removal” determines portions of the model which are either visible or hidden from a current viewpoint. A typical example thereof is the Z Buffer method. The “shading” determines color and brightness of each portion of the object to be seen under the lighting, and applies the determined color to a corresponding pixel on the screen. The “measure for giving reality” is usually carried out after rendering. This measure is required because (1) each graphics processing step up to the rendering is based on the assumption that a surface of an object is a completely smooth curved surface which can be represented by ideal planes or mathematical expressions or that colors on the surface are constant for each plane, and (2) an image obtained by the steps of coordinate conversion → hidden surface removal → shading is inorganic and far from the real object. One example of the “measure for giving reality” is mapping, that is, a process for pasting pre-created pattern data on a surface and/or plane of an object.
Mapping is important for realistically representing the material characteristics of an object. One example thereof is texture mapping in which texture means a pattern or image representing a feeling of material of an object surface (or design of the surface) without a thickness. Texture mapping is done by preparing a texture of each material (e.g. marble stone, bark, aluminum, or the like) as a bitmap in advance, and pasting the texture on a relatively smooth plane or curved surface of the object immediately after the rendering process is ended. According to such a texture mapping, the object having a monotonous surface can be made look like a real one having a complex surface. For example, in a flight simulator, an image of a scene photographed beforehand is texture-mapped on the background to generate a virtual reality picture quickly. It is also possible to make a simple solid model look like a metallic one or stone.
Texture mapping requires access to an enormous amount of data and involves a great deal of computation processing. This is because the amount of texture data (i.e. two-dimensional array data representing an image such as patterns to be pasted, background, etc.) is enormous. Consequently, real time operations for the texture mapping must unavoidably be done in parallel by providing a plurality of pipelines; it is almost impossible to cope with such texture mapping by a single unit. Parallel processing for the texture mapping is done, for example, by dividing a screen into a plurality of areas and distributing processing operations for each of the divided areas among parallel processors.
FIG. 6
shows a schematic block diagram of a hardware configuration of a multiprocessor system
100
. In
FIG. 6
, a multiprocessor system
100
comprises a dispatching processor
10
; a plurality of parallel processors
30
-
1
through
30
-
4
(four processors in FIG.
6
); first-in first-out (FIFO) buffers
50
-
1
through
50
-
4
, one for each of the parallel processors
30
-
1
through
30
-
4
; and a merging processor
40
. The dispatching processor
10
is a computing unit for distributing data sets (a unit of data to be distributed is referred to as a “data set” in this specification) received sequentially to each of the parallel processors
30
-
1
through
30
-
4
according to the attribute of data, etc. The FIFOs
50
-
1
through
50
-
4
are disposed before the corresponding parallel processors
30
-
1
through
30
-
4
, respectively, and enabled to store distributed data sets temporarily and send the data sets sequentially to the parallel processors
30
-
1
through
30
-
4
as they complete data processing for the preceding data sets. The merging processor
40
is a computing unit for integrating data sets distributed by the dispatching processor
10
and processed by the parallel processors
30
-
1
through
30
-
4
again and outputting the integrated data sets.
In the multiprocessor system, it is desirable that a load (i.e. an amount of data processed per unit time) is evenly imposed on each of the parallel processors. If loads are evenly distributed, it is possible to perform efficient parallel processing and the overall performance of the system would be improved in proportion to the number of pipelines (i.e. parallel processors). For example, the system
100
shown in
FIG. 6
is considered to be well-balanced in design in case the total processing speed of all the parallel processors is equal to the speed of data input to the system
100
. In other words, if the loads are unevenly distributed, it would be impossible to benefit from the distributed processing.
In the multiprocessor system
100
shown in
FIG. 6
, the amount of data (load) distributed to each of the parallel processors
30
-
1
through
30
-
4
may become uneven relatively often. For example, this occurs when data sets are unevenly distributed among the parallel processors as shown in Cases (a), (b), and (c) in FIG.
7
. Also, even if the load imposed on each of the parallel processors
30
-
1
through
30
-
4
is even or uniform on average in a long time period, the load may often become uneven at a certain point of time depending on the order of data sets arrange

Affiliated with

Also associated with

Rating

Data processing system and multiprocessor system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data processing system and multiprocessor system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing system and multiprocessor system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3341774