Multi-threaded processing design in architecture with multiple co-processors

• US 20050262510A1
• Filed: 05/12/2005
• Published: 11/24/2005
• Est. Priority Date: 05/13/2004
• Status: Active Grant

• Current Assignee: Ittiam Systems Pte Ltd
• Original Assignee: Ittiam Systems Pte Ltd
• Inventors: Kumar, Dinesh, Parameswaran, Sankaranarayanan, Tamia, Dileep Kumar, Singhal, Manish, Kulkarni, Aditya, Sethuraman, Sriram, Muthukrishnan, Murali Babu
• Granted Patent: US 7,634,776 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 15/7842 on one IC chip (single chip microcontrollers)
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence

Abstract

A method for designing a multi-threaded processing operation that includes, e.g., multimedia encoding/decoding, uses an architecture having multiple processors and optional hardware accelerators. The method includes the steps of: identifying a desired chronological sequence of processing stages for processing input data including identifying interdependencies of said processing stages; allotting each said processing sage to a processor; staggering the processing to accommodate the interdependencies; selecting a processing operation based on said allotting to arrive at a subset of possible pipelines that offer low average processing time; and, choosing one design pipeline from said subset to result in overall timing reduction to complete said processing operation. The invention provides a multi-threaded processing pipeline that is applicable in a System-on-Chip (SoC) using a DSP and shared resources such as DMA controller and on-chip memory, for increasing the throughput. The invention also provides an article which is programmed to execute the method.

Claims

1. A method for designing a processing operation in an architecture that uses multiple processors, comprising the steps of:

identifying a chronological sequence of processing stages for processing input data including identifying interdependencies of said processing stages;

allotting each said processing stage to a processor;

staggering the processing to accommodate said interdependencies;

selecting a subset of possible pipelines that offer low average processing time, based on said allotment; and

,

choosing one design pipeline that offers overall timing reduction in presence of statistical variations to complete said processing operation.

2. The method as in claim 1 including the step of assigning one or more data buffers to each processing stage on each processor, based on said interdependencies;

and,

ensuring that the step of allocating is done so that a constraint that no two processors can access a given buffer simultaneously is met.

3. The method as in claim 2, including a step wherein a given processor can access one of two given buffers and not a third one, at a given time.

4. The method as in claim 1, including a step wherein said multiple processors share memory, and wherein said step of allotting and selecting a processing operation is done considering possible staggering variations in said processing without breaking dependencies and predetermined platform constraints.

5. The method as in claim 1, wherein after the step of choosing one design pipeline, the method includes the steps of identifying one or more processors that are on a critical timing path, and selectively moving at least some tasks from said identified processor to other processors that could perform said moved tasks.

6. The method as in claim 1, wherein said processing operation includes video encoding, and wherein said chronological sequence of processing stages includes motion estimation, motion compensation, forward transform, quantization, inverse quantization, inverse transform and reconstruction.

7. The method as in claim 6, wherein said step of allotting comprises handling input data as macroblock-pairs instead of single macroblocks.

8. The method as in claim 1, wherein said processing operation includes video decoding, and where said chronological sequence of processing stages includes:

sequence1 comprising macroblocks (MB) parameters decoding, motion vectors decoding, and variable length decoding; and

sequence 2 comprising inverse quantization, inverse transform, and motion compensation, wherein further the design pipeline is spread over 3 MBs.

9. The method as in claim 1, wherein said processing operation includes audio decoding, and wherein said chronological sequence of processing stages includes:

sequence 1 comprising header parameters decoding and variable length decoding, and sequence 2 comprising inverse quantization, inverse transform and windowing.

10. The method as in claim 1, wherein said processing operation includes audio encoding and wherein said chronological sequence of processing stages includes psycho acoustic modeling, filtering by masking, sub-band decomposition, transform quantization and variable length encoding.

11. The method as in claim 1 wherein said multiprocessors include coprocessors and accelerators, and wherein said process operation includes video/audio processing, the method including the step of breaking up various tasks in said processing operation at a desired granularity, wherein further said step of choosing one design pipeline includes reducing idle time of co-processors/accelerators on a chosen critical path.

12. The method as in claim 11, including the step of allotting processing stages as tasks on different coprocessors so as to achieve substantially balanced load.

13. The method as in claim 1 including the step of fetching/storing necessary data from/to external memory over DMA (direct memory access) to reduce waiting time.

14. The method as in claim 11, including the step of keeping as many coprocessors/accelerators as possible active at any given time.

15. The method as in claim 9, including the step of providing data arrangements in which multiple MACs (multiply and accumulate units) access data to map from staggered addressing to circular addressing for audio decoding.

17. The method of claim 1, wherein the processing operation includes a master DSP (digital signal processor) and coprocessors, including the step of minimizing a number of set-ups needed from said master DSP by manipulating a control sequence on said coprocessors without DSP intervention.

18. The method as in claim 11, wherein said chosen design pipeline is a conditional pipeline that realizes overall processing throughput gain even though certain processing steps are skipped on only one or two coprocessors/accelerators.

19. The method as in claim 11, wherein said process operation includes a DSP, the method including the step of assigning a multi-MAC coprocessor to do computations including filtering, transforms, and mean squared error computation, and assigning a programmable coprocessor to do non-normative tasks.

16. The method as in clam 11, including the step of creating predetermined sets of command sequences for programmable coprocessors, to reduce dynamic set up overhead costs.

20. A method for achieving efficient parallel processing multi-thread-design-capability in architecture which uses multiple processor units and is capable of handling multi-media encoding/decoding, comprising the steps of:

identifying different processing stages for and their interdependencies during processing input data;

assigning each said processing stage to a suitable processing unit;

staggering said processing stages to accommodate said interdependencies;

assigning a buffer, by mapping, to each processing unit for each processing stage;

ascertaining processing time needed, on respective mapped processing units, for fixed complexity processing stages and varying complexity processing stages;

based on an average processing time and other predetermined constraints, selecting a subset of possible timelines that offer a best average processing time; and

,

from the subset of possible timelines, selecting a single design pipeline that offers best timing.

21. The method as in claim 20, including the step of ensuring that no two processing units can simultaneously access a known buffer, and ensuring that out of every three buffers, two buffers are visible mutually exclusively.

22. The method as in claim 20, including the step of listing mutually exclusive modes of said processing stages including a frequency of occurrence of said listed mutually exclusive modes.

23. The method as in claim 20, including the step of using shared buffers and moving data from an external memory to said shared buffers in said processing stages.

24. The method as in claim 20, including the step of, on said selected design pipeline, identifying a processing unit that uses said best timing and is on a critical path, and moving away any tasks currently scheduled on the identified processing unit, if such tasks can be performed on other processing units.

25. An article comprising a storage medium having instructions that when executed by a computing platform result in execution of a method for designing a processing operation in an architecture that uses multiple processors, comprising the steps of:

identifying a chronological sequence of processing stages for processing input data including identifying interdependencies of said processing stages;

allotting each said processing stage to a processor;

staggering the processing to accommodate said interdependencies;

selecting a subset of possible pipelines that offer low average processing time, based on said allotment; and

,

choosing one design pipeline that offers overall timing reduction in presence of statistical variations to complete said processing operation.

26. The article as in claim 25 wherein said method includes the step of assigning one or more data buffers to each processing stage on each processor, based on said interdependencies;

and,

ensuring that the step of allocating is done so that a constraint that no two processors can access a given buffer simultaneously is met.

27. An article comprising a storage medium having instructions that when executed by a computing platform result in execution of a method for designing a processing operation in an architecture that uses multiple processors, comprising the steps of:

identifying a desired chronological sequence of processing stages for processing input data including identifying interdependencies of said processing stages;

allotting each said processing stage to a suitable processor;

staggering the processing on said allotted processors to accommodate said interdependencies;

selecting a subset of possible pipelines that offer low average processing time based on said allotment; and

,

choosing one design pipeline from said subset to result in overall timing reduction to complete said processing operation,

wherein said multiprocessors include processors and accelerators, and wherein said process operation includes video/audio processing, the method including the step of breaking up various tasks in said processing operation at a desired granularity, wherein further said step of choosing one design pipeline includes reducing idle time of co-processors/accelerators on a chosen critical path.