Massively parallel digital image data processor using pixel-mapped input/output and relative indexed addressing

• US 5,253,308 A
• Filed: 06/21/1989
• Issued: 10/12/1993
• Est. Priority Date: 06/21/1989
• Status: Expired due to Fees

• Current Assignee: Amber Engineering, Inc. (Rtx Corporation)
• Original Assignee: Amber Engineering, Inc. (Rtx Corporation)
• Inventors: Johnson, William K.
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): Jung, Yon
• Application Number:
  US07/369,257
• Time in Patent Office: 1,574 Days
• Field of Search: 382/41, 382/49, 382/27, 364/200, 364/716, 364/518
• US Class Current: 382/304
• CPC Class Codes: G06F 15/8023 Two dimensional arrays, e.g. mesh, torus
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining

Abstract

A massively parallel digital image data processor provides a large number of processing elements arranged in a two-dimensional matrix form. Relative indexed addressing among the processing elements is provided, whereby image data may be easily accessed by and shared among all processing elements. A single-instruction/multiple-data (SIMD) architecture provides instructions to the processing elements in parallel in accordance with specific application programs therefor. The processing elements use triple-ported register files for their internal memory which may input and output data independently and simultaneously. The processing elements are memory-mapped into the address space of the processor'"'"'s embedded computer to simplify addressing thereof. All image data is inputted and outputted in pixel format. All image data is transferred, stored and processed in bit-serial format.

Claims

1. An image processing system for processing image data provided by an external image sensor which provides digital image data having a predetermined number of bits of data corresponding to a predetermined number of pixels, said processing system comprising:

a plurality of interconnected processing elements for receiving and processing said digital image data, each of said processing elements comprising;

storage means for storing received and processed digital image data;

arithmetic-logic means, coupled to said storage means and receiving data therefrom, for performing arithmetic and logical binary operations upon said data received from said storage means and for outputting results of said arithmetic and logical binary operations to said storage means as processed digital image data;

first bussing means, coupled to said processing elements for receiving said digital image data from said sensor and routing said digital image data to said processing elements;

second bussing means, coupled to aid processing elements for routing said processed digital image data from said processing elements;

controller means for controlling said routing of said digital image data to and from said processing elements along said first and second bussing means and for controlling said processing elements; and

image to processing element correspondence means for coordinating the routing of said image data between said controller means and said plurality of processing elements and for coordination of the processing of said image data so as to provide a virtual correspondence between said pixels and said processing elements independently of the relative number of said pixels and said processing elements.

2. A processing system as set out in claim 1, wherein said storage means comprises a multi-ported register file memory comprising an input data port, a first output data port, a second output data port, an input data port address input, a first output data port address input and a second output data port address input.

3. A processing system as set out in claim 2, wherein said input data port address input and said first and second output data port address inputs of said multi-ported register file memory may be individually and independently addressed and enabled.

4. A processing system as set out in claim 2, wherein said input data port of said multi-ported register file memory may input data independently and simultaneously as data is outputted from said first output data port and said second output data port of said multi-ported register file memory.

5. A processing system as set out in claim 1, wherein each of said processing elements further comprises an input data multiplexer having a plurality of selectable input data ports and an output data port, wherein said output data port is coupled to said storage means.

6. A processing system as set out in claim 5, wherein said digital image data received by said processing elements is provided in pixel parallel form.

7. A processing system as set out in claim 6, wherein each of said processing elements further comprises a parallel-to-serial digital data converter having a parallel input data port and a serial output data port, wherein said serial output data port is coupled to one of said selectable input data ports of said input data multiplexer.

8. A processing system as set out in claim 6, wherein each of said processing elements further comprises a serial-to-parallel digital data converter having a serial input data port and a parallel output data port, wherein said serial input data port is coupled to said output data port of said input data multiplexer.

9. A processing system as set out in claim 1, wherein each of said processing elements further comprises a data storage transceiver means for transmitting data to and receiving data from data memory devices external to and associated with said processing element.

10. A processing system as set out in claim 1, wherein each of said processing elements further comprises a data transfer transceiver means for transmitting data to and receiving data from other processing elements within said plurality of processing elements.

11. A processing system as set out in claim 9, wherein said data storage transceiver means comprises a single bi-directional signal path having a signal transceiver at each end.

12. A processing system as set out in claim 11, wherein said signal path and transceivers convey said data in serial form.

13. A processing system as set out in claim 11, wherein said signal path and transceivers convey said data in parallel form.

14. A processing system as set out in claim 9, wherein said data storage transceiver means comprises a transmitting signal path and a separate receiving signal path, said transmitting signal path originating with a signal driver and said receiving signal path terminating with a signal receiver.

15. A processing system as set out in claim 14, wherein said signal paths, signal driver and signal receiver convey said data in serial form.

16. A processing system as set out in claim 14, wherein said signal paths, signal driver and signal receiver convey said data in parallel form.

17. A processing system as set out in claim 10, wherein said data transfer transceiver means comprises a single bi-directional signal path having a signal transceiver at each end.

18. A processing system as set out in claim 17, wherein said signal path and transceiver convey said data in serial form.

19. A processing system as set out in claim 17, wherein said signal path and transceiver convey said data in parallel form.

20. A processing system as set out in claim 10, wherein said data transfer transceiver means comprises separate transmitting and receiving signal paths, said transmitting signal path originating with a signal driver and said receiving signal path terminating with a signal receiver.

21. A processing system as set out in claim 20, wherein said signal paths, signal driver and signal receiver convey said data in serial form.

22. A processing system as set out in claim 20, wherein said signal paths, signal driver and signal receiver convey said data in parallel form.

45. An image processing system as set out in claim 1 wherein said plurality of processing elements are electrically configured in an array and wherein said correspondence means comprises:

means for mapping said predetermined number of pixels to sad plurality of processing elements, wherein said predetermined number of pixels may vary and may be greater than the number of said processing elements; and

means for controlling the accessing of image data of a pixel for processing by a first one of said processing elements, from the storage means of a second one of said pixel processing elements, base upon the relative position of said pixel to a base pixel stored in a first processing element within said array.

23. An image processing system for processing image data provided by an external image sensor which provides digital image data having a predetermined number of bits of data, said processing system comprising:

a plurality of interconnected processing elements for receiving and processing said digital image data to provide processed digital image data, said plurality of processing elements being electrically configured in a two-dimensional matrix, said matrix comprising a plurality of rows and a plurality of columns in which a processing element is electrically located at the intersection of each row and each column, each of said processing elements having an address corresponding to the respective row and column in which each processing element lies;

first bussing means, coupled to said processing elements for receiving said digital image data from said sensor and routing said digital image data to said processing elements;

second bussing means, coupled to said processing elements for routing said processed digital image data from said processing elements; and

controller means for controlling said routing of said digital image data to and from said processing elements along said first and second bussing means and for controlling said processing elements and for directly and randomly accessing image data in said processing elements, said controller means including a memory having a plurality of address locations, wherein said address locations correspond to said addresses of said processing elements, such that said addresses of said processing elements are memory-mapped into said controller means.

25. A processing system as set out in claim 23, wherein said first bussing means comprises a plurality of parallel signal paths.

27. A processing system as set out in claim 25, wherein said plurality of parallel signal paths equals said predetermined number of bits of data.

28. A processing system as set out in claim 23, wherein said second bussing means comprises a plurality of parallel signal paths.

31. A processing system as set out in claim 23, wherein said controller means comprises a plurality of control signal paths for conveying control signals from a computer.

33. A processing system as set out in claim 23, wherein said controller means comprises a microprocessor and associated memory elements containing microcoded commands.

24. An image processing system for processing digital image data having a predetermined number of bits of data corresponding to an image having a plurality of pixels arranged in a matrix, said processing system comprising:

a plurality of interconnected processing elements for receiving and processing said digital image data, said plurality of processing elements being electrically configured in an array;

data transfer means for transmitting data to and receiving data from other processing elements within said plurality of processing elements;

first bussing means, coupled to said processing elements for receiving said digital image data and routing said digital image data to said processing elements;

second bussing means, coupled to said processing elements for routing said processed digital image data from said processing elements; and

controller means for controlling said routing of said digital image data to and from said processing elements along said first and second bussing means and for controlling said processing elements, said control of said processing elements comprising controlling accessing of image data corresponding to a target pixel stored in a first one of said processing elements and instructing a second of said processing elements to receive and process the target pixel image data from said first one of said processing elements, based upon a relative indexed address, wherein said relative indexed address corresponds to the number of rows and number of columns of said matrix separating said base pixel in said second processing element receiving said image data from said target pixel in said first processing element from which said image data is to be received.

26. A processing system as set out in claim 24, wherein said first bussing means comprises a plurality of parallel signal paths.

29. A processing system as set out in claim 24, wherein said second bussing means comprises a plurality of parallel signal paths.

30. A processing system as set out in claim 26, wherein said plurality of parallel signal paths equals said predetermined number of bits of data.

32. A processing system as set out in claim 24, wherein said controller means comprises a plurality of control signal paths for conveying control signals from a computer.

34. A processing system as set out in claim 24, wherein said controller means comprises a microprocessor and associated memory elements containing microcoded commands.

35. An image processing system for processing image data provided by an external image sensor which provides digital image data having a predetermined number of bits of data, said processing system comprising:

a plurality of interconnected processing elements for receiving and processing said digital image data, said plurality of processing elements being electrically configured in a two-dimensional matrix comprising a plurality of rows and a plurality of columns in which a processing element is electrically located at the intersection of each row and each column and the respective address for each of said processing elements corresponds to the respective row and column in which each processing element lies, each processing element including a relative address generator circuit comprising;

first instruction reception means for receiving first microcode instructions indicative of, a relative digital memory location being relative to a reference digital memory location, said digital memory locations each containing a plurality of digital bits therein;

first decoding means for decoding said first microcode instructions into said relative address data, said relative address data being representative of a relative digital memory location;

second instruction reception means for receiving second microcode instructions indicative of bit data, said bit data being representative of a digital bit located within said relative digital memory location;

first address data reception means for receiving direct address data, said direct address data being representative of said digital bit;

first selection means for selecting a range of possible values for said relative address data;

second selection means for selecting a number of said digital bits to be represented by said bit data;

combination means for combining said relative address data with said bit data to create relative indexed address data; and

third selection means for selecting between said relative indexed address data and said direct address data; and

controller means for controlling routing of said digital image data to and from said processing elements and for controlling said processing elements, said control of said processing elements comprising provision of first and second microcode instructions and first address data to said processing elements when instructing said processing elements to receive and process image data from other processing elements.

36. A relative address generator circuit as set out in claim 35, wherein said first instruction reception means comprises a row address instruction reception means and a column address instruction reception means.

37. A relative address generator circuit as set out in claim 36, wherein said row and column address instruction means each comprise a digital counter, each of said digital counters being capable of being preset to a selectable value and incremented and decremented therefrom.

38. A relative address generator circuit as set out in claim 35, wherein said first decoding means comprises first and second programmable memory devices having address inputs and data outputs, said address inputs of said first programmable memory devices being coupled to said digital row counter, said address inputs of said second programmable memory devices being coupled to said digital column counter, said data outputs of said programmable memory devices comprising said relative address data.

39. A relative address generator circuit as set out in claim 35, wherein said second instruction reception means comprises a digital register.

40. A relative address generator circuit as set out in claim 35, wherein said first address data reception means comprises a digital counter capable of being preset to a selectable value and incremented and decremented therefrom under program direction.

41. A relative address generator circuit as set out in claim 35, wherein said first and second selection means and said combination means together comprise a matrix of electrical jumper connections.

42. A relative address generator circuit as set out in claim 35, wherein said third selection means comprises digital registers having tri-state output data ports.

43. A relative address generator circuit as set out in claim 35, wherein said third selection means comprises digital registers having tri state output data ports.

44. An image processing method for processing digital image data having a predetermined number of bits of data corresponding to the pixels of an image having a matrix of pixels by a plurality of processing elements electrically configured and interconnected in a two-dimensional array, said pixel matrix having a plurality of rows and a plurality of columns, said processing method comprising the steps of:

routing said digital image data to said plurality of processing elements;

selectively storing said digital image data associatively with respect to said processing elements;

accessing and acquiring, by a first processing element, digital image data corresponding to a target pixel initially stored associatively with respect to a second processing element, said first processing element accessing said digital image data by specifying the relative location of said target pixel relative to the location of base pixel in said first processing element within said matrix of pixels, said relative location corresponding to the number of said rows and number of said columns separating said target pixel and base pixel;

processing said accessed and acquired digital image data arithmetically and logically, selectably, within said processing elements; and

routing said processed digital image data out from said plurality of processing elements.