Source: https://patents.google.com/patent/US6693643B1/en
Timestamp: 2020-04-04 18:56:40
Document Index: 646541303

Matched Legal Cases: ['ART) 1515', 'ART 1515', 'ART) 1805', 'ART 1805', 'ART 1805', 'ART 1805', 'ART 2107', 'ART 2107', 'ART 2107', 'ART 2108']

US6693643B1 - Method and apparatus for color space conversion - Google Patents
US6693643B1
US6693643B1 US10/038,301 US3830101A US6693643B1 US 6693643 B1 US6693643 B1 US 6693643B1 US 3830101 A US3830101 A US 3830101A US 6693643 B1 US6693643 B1 US 6693643B1
US10/038,301
Steven Todd Weybrew
2001-12-31 Application filed by Apple Computer Inc filed Critical Apple Computer Inc
2001-12-31 Priority to US10/038,301 priority Critical patent/US6693643B1/en
2002-05-31 Assigned to APPLE COMPUTER, INC. reassignment APPLE COMPUTER, INC. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: OUZILEVSKI, ALEXEI V., WEYBREW STEVEN TODD, TRIVEDI, SUSHMA SHRIKANT
2004-02-17 Publication of US6693643B1 publication Critical patent/US6693643B1/en
Methods and apparatuses for converting color components in one space to those in another space. In one aspect of the invention, a method for vector conversion including: loading a first vector of components into a vector register; generating a first vector of indices in a vector register, each index of the first vector of indices being one of the first vector of components, at least one component in the first vector of components being replicated as a plurality of duplicated indices in the first vector of indices; looking up simultaneously a first vector of data items from a plurality of look up tables using the first vector of indices; and summing up at least one subset of the first vector of data items into at least one component of a second vector of components.
The invention relates to data processing systems using vector processing and Very Long Instruction Word (VLIW) architecture, more particularly to color space conversion.
In the above instructions, Vec_max selects the larger ones from the elements of vector vA and the corresponding elements of vector vB to produce vMax; on the other hand, Vec_min selects the smaller ones from the elements of vA and the corresponding elements of vB to produce vector vMin; and Vec_sub subtracts vMin from vMax to produce vector vResult, which is the absolute difference of vectors vA and vB. Such a method takes two vector registers for the storage of intermediate results and three instructions to obtain the absolute difference of two vectors of numbers.
While this approach can be used to perform table look-up for a vector of data from a single small look-up table, there are severe limitations in its practical applications in processing large look-up tables. The indices for the look-up tables must be preprocessed to generate the index information in vector vI. The size of the table that can be used in a table look-up in a single instruction is restricted by the number of bits allocated to represent the index information in vector vI, and by the total number of data elements that can be held by vector registers vA and vB. In a typical vector processor, two vector registers (vA and vB) can hold only 32 8-bit data elements. In general, it is necessary to use a program of multiple sequential instructions to implement vector look-up using one or an array of look-up tables. Further, due to the limited size of a vector register file, only a part of look-up table entries may be loaded into the vector register file when large look-up tables are used. Thus, when a set of large look-up tables are used, table look-up for a vector of data elements requires repeatedly loading table entries into the vector register file. Thus, it can be a very inefficient operation.
Since many applications, such as software programs for computing pixel values in image processing, require the mapping of a set of values to another set of values in using a set of different tables, it is desirable to have an efficient method to perform table look-up for a vector of data elements.
Blending two images into a new image is a common operation in many applications. For example, a video editing application may blend the images from two different video streams to create a new video stream with special effects. The general blending equation for computing an attribute of a pixel in a new image using those in two source images can be written as:
D=K 1*S 1+K 2*S 2
where D is the resulting attribute of the pixel; S1 and S2 are the attributes of the pixel in the source images; and K1 and K2 are the blending factors for the corresponding source images.
The blending factors may be constants, but are more generally functions of alpha1 and/or alpha2. In the most common case, K1 equals alpha1 and K2 equals one minus alpha1. The alpha values, known as “alpha” in the graphics world and “key” in the video world, generally represent the desired opacity of the associated image pixel. Generally, the alpha value is not constant over an entire image.
Blending is generally implemented using 32 bit, EEE 754 compliant floating point arithmetic to avoid visually distracting artifacts. However, video source data, including “key”, is usually supplied in 8 or 10 bit integer format for each attribute; hence it is normally required to convert the integer source data to floating point data before applying the general blend equation and then convert the result back to integer data post blending.
To edit video streams, a video editing software application may be required to decode in real time several video streams in order to create video effects, such as blending of video sequences, picture in picture, titling, etc. The resulting uncompressed video images obtained after editing need to be compressed for storage. Compression/decompression of video data is an expensive operation. Addin-boards are frequently used to accelerate the process of compressing or decompressing video data. Since such add-in-boards are quite expensive, video editing so far has been in the domain for video professionals. Consumer video editing software applications implemented on general purpose processors are slow and suffer from poor quality due to massive computation requirements.
The DV format, such as DV25 or DV50, due to its linear nature (i.e., the consecutive frames of video data are encoded in their display order), relatively low information loss (by using high bit rate coding) and the constant bit rate (i.e., each compressed frame has a constant size) is a preferred format for video editing on the desktop computers. Most of the digital video cameras produce DV bit streams. The compression and decompression processes of DV video streams are briefly outlined below.
DV compression belongs to a family of constant bit rate block based transform coding techniques. The input to a DV encoder is a 29.97 frames per second digital video stream in YUV color space. DV standards support various sampling structures in YUV color space, such as 4:1:1, 4:2:0 and 4:2:2 image sampling structures. An input video stream is processed in the units of 8×8 two-dimensional blocks of pixels. Blocks are organized into macro blocks, each consisting of four or six 8×8 pixel blocks. Macro blocks are organized into segments. A segment comprises 5 macro blocks (e.g., 30 blocks) and is compressed into a constant 400-byte bit stream.
Following the traditional transform coding approach, each pixel block is transformed into frequency domain using Forward Discrete Cosine Transformation (FDCT). The transformed coefficients are further quantized and entropy coded with variable length code words. Each compressed macro block in a segment has a header and a number of fixed size blocks (e.g., 4 luminance blocks and 2 chrominance blocks). In a segment, the code words for each block are concatenated before being distributed into the corresponding compressed-data area for the block in pass 1. In pass 2, the remaining of the blocks after the pass 1 operation that cannot be fitted into the corresponding compressed-data area are distributed in to their corresponding compressed macro block. In pass 3, the remainder after the pass 2 operation are distributed into the video segment.
The decompression process creates pixel data from a DV bit stream by performing reverse operations, namely Variable Length Decoding (VLD), Inverse Scaling (IS) and Inverse Discrete Cosine Transform (IDCT). Since code words are distributed in a segment in 3 passes, three corresponding passes of VLD operations can be used to recover all the information encoded using variable length code words.
The documentation of standards IEC 61834 and SMPTE 314M contains detailed descriptions about DV standards. Other video standards and image formats, such as MPEG and JPEG, also involves discrete cosine transformation, quantization, and variable length decoding. The general procedure to compress and decompress such video streams or images are the same.
Various implementations of DV decoders currently exist in the industry. Some dedicated chipsets are used in hardware implementations; and there are software applications for general purpose processors. The drawbacks of the hardware implementations using dedicated chipsets are the high cost, lack of scalability, and lack of compatibility with other components in video systems. The drawback of the software decoders on the general purpose CPUs is that the performance of a decoder highly depends on the computing environment, such as the run time usages of the CPU, memory, cache, and I/O devices. The instruction sets of general purpose processors are not well suited for processing encoded bit streams.
Variable Length Decoding (VLD), when implemented on a general purpose processor, is limited in performance by the operations for table look-up and conditional branch. The Huffman code used in a DV video stream can be up to 16 bits in length. One of the most efficient methods to perform VLD on a general purpose processor is to use a single look-up table. However, the single look-up table contains 64 K entries, each entry consisting of a triplet of {run, level, code length}. Since each entry stored in system memory may require 16 bits, the single look-up table may require 128 Kbytes of system memory. The look-up table may be resident in the system memory. A single look-up table approach is highly inefficient from caching point of view. The cache miss penalty can dramatically reduce the performance. Multi-table approaches reduce the amount of memory required by the look-up table by looking-up sequentially in a number of smaller look-up tables, and thus suffers from increased execution time due to multiple sequential look-up operations and associated overheads.
The video editing applications require decoding several video streams simultaneously. Further, with High Definition TV (HDTV), the amount of processing power required for decompression can be very high. Thus, it is desirable to have efficient methods and apparatuses for variable length decoding bit streams.
Methods and apparatuses for converting color components in one space to those in another space are described here.
In one aspect of the invention, a method for vector conversion including: loading a first vector of components into a vector register; generating a first vector of indices in a vector register, each index of the first vector of indices being one of the first vector of components, at least one component in the first vector of components being replicated as a plurality of duplicated indices in the first vector of indices; looking up simultaneously a first vector of data items from a plurality of look up tables using the first vector of indices; and summing up at least one subset of the first vector of data items into at least one component of a second vector of components. In one example, a component of the first vector of components is replicated as a plurality of duplicated indices in the first vector of indices for looking up respectively a plurality of bit segments of one data item of extended precision in the first vector of data items. The first vector of data items looked up from the plurality of look up tables are so aligned in a vector register that the component of the second vector can be computed using a vector sum across instruction or a vector sum across partial instruction. In one example according to this aspect, the first and second vectors of components are vectors of color components in two different color spaces (e.g., YCrCb, RGB, YUV, YIQ, HSI, HSV, HLS or others).
FIG. 2 shows another configuration of a computer system, which may be used by the present invention.
FIG. 4A shows a media processor used in a compute system.
FIG. 4B shows an embodiment of the present invention.
FIG. 5A shows a conventional media processor.
FIG. 5B shows another embodiment of the present invention.
FIG. 6 shows another method for memory access used in one embodiment of the present invention.
FIG. 7 shows one embodiment of memory controller used in an embodiment of the present invention.
FIG. 8 shows an embodiment of memory interfaces used in the present invention.
FIG. 9 shows an example of an entry in one embodiment of the memory address re-mapping table of the present invention.
FIG. 10A shows another example of an entry in one embodiment of the memory address re-mapping table of the present invention.
FIG. 10B shows an example of a PCI-0 mask register used in one embodiment of the present invention.
FIG. 11 shows a configuration of a memory mapping used in one embodiment of the present invention.
FIG. 12 shows an embodiment of a method accessing the memory address re-mapping table.
FIG. 13 shows another embodiment of a method accessing the memory address re-mapping table.
FIG. 14 shows yet another embodiment of a method accessing the memory address re-mapping table.
FIG. 15 shows yet another aspect of an embodiment of a method accessing the memory address re-mapping table.
FIG. 16 shows yet another aspect of an embodiment of a method accessing the memory address re-mapping table.
FIG. 17 shows an example of a compute engine used in one embodiment of the present invention.
FIG. 18 shows another embodiment of a compute engine used in the present invention.
FIG. 19A shows an embodiment of an instruction unit of a compute engine used in the present invention.
FIG. 19B shows another embodiment of an instruction unit of a compute engine used in the present invention.
FIG. 20A shows a method accessing a command queue used in one embodiment of the present invention.
FIG. 20B shows another method accessing a command queue used in one embodiment of the present invention.
FIG. 21 shows an embodiment of a configuration of a command queue used in the present invention.
FIG. 22 shows an example of a command queue entry of the present invention.
FIG. 23 shows an example of the instruction priorities used in one embodiment of the present invention.
FIG. 24 shows an embodiment of dispatching instructions of the present invention.
FIG. 25 shows another embodiment of dispatching instructions of the present invention.
FIG. 26 shows an example of latency of instructions used in the present invention.
FIG. 27 shows yet another embodiment of dispatching instructions of the present invention.
FIG. 28 shows yet another embodiment of dispatching instructions of the present invention.
FIG. 29 shows an example of the interrupt control registers of the invention.
FIG. 30 shows another example of the interrupt control registers of the invention.
FIG. 31 shows a flow diagram illustrating the general steps used by a processor to manipulate data in executing an instruction according to one embodiment of the invention.
FIG. 32 illustrates a block diagram representation of a circuit for the execution of a method to compute an absolute difference of two vectors of numbers according to one embodiment of the present invention.
FIG. 33 illustrates a block diagram representation of a circuit for the execution of a method to compute an absolute difference of two numbers according to one embodiment of the present invention.
FIG. 34 illustrates data representations for the execution of an instruction for the computation of absolute difference of two vectors of numbers according to one embodiment of the present invention.
FIG. 35 shows a flow diagram for a method of computing the absolute difference of two vectors of numbers according to one embodiment of the present invention.
FIG. 36 shows a flow diagram for a method of computing the absolute difference of two numbers according to one embodiment of the present invention.
FIG. 37 illustrates a block diagram representation of a circuit for the execution of a method to perform table look-up of a vector of data elements according to one embodiment of the present invention.
FIG. 38 illustrates a block diagram representation of a circuit for configuring look-up units into different look-up tables according to one embodiment of the present invention.
FIG. 39 illustrates another block diagram representation of a circuit for configuring look-up units into different look-up tables according to one embodiment of the present invention.
FIG. 40 illustrates data representations for the execution of an instruction for performing table look-up of a vector of data elements according to one embodiment of the present invention.
FIGS. 41-43 illustrate block diagram representations of circuits for performing table look-up of vectors of different sizes using a set of look up units according to one embodiment of the present invention.
FIG. 44 shows a flow diagram for a method to perform table look-up of a vector of data elements according to one embodiment of the present invention.
FIG. 45 illustrates a block diagram representation of a circuit for the execution of a method to load entries in look-up units using DMA controllers according to one embodiment of the present invention.
FIG. 46 illustrates data representations for the execution of a method to load entries in look-up units using DMA controllers according to one embodiment of the present invention.
FIG. 47 shows a flow diagram for a method to load entries in look-up units using DMA controllers according to one embodiment of the present invention.
FIG. 48 illustrates a block diagram representation of a circuit for the execution of a method to set entries in look-up tables according to one embodiment of the present invention.
FIG. 49 illustrates data representations for the execution of a method to set entries in look-up tables according to one embodiment of the present invention.
FIG. 50 shows a flow diagram for a method to set entries in look-up tables according to one embodiment of the present invention.
FIG. 51 illustrates a block diagram representation of a circuit for the execution of a method to perform variable length decoding according to one embodiment of the present invention.
FIGS. 52-53 illustrate block diagram representations of circuits for performing variable length decoding using a set of look up units according to one embodiment of the present invention.
FIG. 54 illustrates a detailed block diagram representation of a circuit to select a segment of bits from a bit stream according to one embodiment of the present invention.
FIG. 55 illustrates a detailed block diagram representation of a circuit to select a valid data from the look-up results of a number of look-up tables according to one embodiment of the present invention.
FIG. 56 illustrates a detailed block diagram representation of a circuit to format a valid data from a look-up table according to one embodiment of the present invention.
FIG. 57 illustrates a detailed block diagram representation of a circuit to format an escaped data from a bit stream according to one embodiment of the present invention.
FIG. 58 illustrates a detailed block diagram representation of a circuit to format an escaped data obtained from a bit stream according to one embodiment of the present invention.
FIG. 59 illustrates a detailed block diagram representation of a circuit the result of variable length decoding using the escaped data and the data up tables according to one embodiment of the present invention.
FIG. 60 illustrates data representations for the execution of a method to perform variable length decoding according to one embodiment of the present
FIG. 61 shows a flow diagram for a method to perform variable length decoding according to one embodiment of the present invention.
FIG. 62 shows look-up tables for variable length decoding code words encoded using DV standard according to one embodiment of the present invention.
FIG. 63 shows a flow diagram for a method to decode a DV video one stage.
FIG. 64 shows a flow diagram for a method to decode a DV video steam in two stages.
FIG. 65 shows a flow diagram for another method to decode a DV video stream in two stages.
FIG. 66 shows a flow diagram for a method to decode a DV video stream in three stages.
FIG. 67 shows a detailed flow diagram for a method to transfer data while decoding a video stream.
FIG. 68 shows a detailed flow diagram for a method to transfer data while variable length decoding a segment of a video stream.
FIG. 69 shows a detailed flow diagram for a method to transfer data while inverse discrete cosine transforming macro blocks of a video stream.
FIG. 70 shows a memory management scheme for a method to transfer data while decoding a video stream.
FIG. 71 shows a memory management scheme for a method to transfer data while variable length decoding a segment of a video stream.
FIG. 72 shows a memory management scheme for a method to transfer data while inverse discrete cosine transforming macro blocks of a video stream.
FIG. 73 shows a flow diagram for a method to decode a bit stream by using a plurality of execution units concurrently.
FIG. 74 shows a data structure for storing either remaining bits or incomplete code bits.
FIG. 75 shows methods to transpose a matrix using operations that change the positions of the elements within rows or within columns.
FIG. 76 shows examples of indices that may be used in a plurality of look up tables to change the positions of the elements within columns.
FIG. 77 shows a method to transpose a matrix using a vector processor according to one embodiment of the present invention.
FIG. 78 shows a flow chart for a method to transpose a matrix using a VLIW processor according to one embodiment of the present invention.
FIG. 79 shows an example of a method to look up a vector of data items of extended precision according to one embodiment of the present invention.
FIG. 80 shows an example of a method to look up two vectors of data items in parallel for one vector of indices according to one embodiment of the present invention.
FIG. 81 shows an example of a method to look up two vectors of data items in parallel for two vectors of indices according to one embodiment of the present invention.
FIG. 82 shows an example of a method to look up two vectors of data items of extended precision in parallel for one vector of indices according to one embodiment of the present invention.
FIG. 83 shows another example of a method to look up two vectors of data items of extended precision in parallel for one vector of indices according to one embodiment of the present invention.
FIG. 84 shows a method to blend two images using a vector look up unit according to one embodiment of the present invention.
FIG. 85 shows a method to look up vectors of blending factors using a vector look up unit according to one embodiment of the present invention.
FIG. 86 shows a method to look up two vectors of data items in parallel for two vectors of indices using a vector look up unit according to one embodiment of the present invention.
FIGS. 87-89 show flow charts for methods to look up two vectors of data items in parallel for one or two vectors of indices.
FIG. 90 shows an example of a method to convert a vector of elements into another vector of elements using a vector look up unit according to one embodiment of the present invention.
FIG. 91 shows an example of a method to convert a vector of elements into another an element of another vector using extended precision in a vector look up unit according to one embodiment of the present invention.
FIG. 92 shows a flow chart for a method to convert a vector of elements into another vector of elements using a vector processor according to one embodiment of the present invention.
FIG. 93 shows a flow chart for a method to convert a vector of elements into another vector of elements using a VLIW processor according to one embodiment of the present invention.
FIG. 94 shows a method to encode a DV video stream in three stages.
FIG. 95 shows a memory management scheme for a method to transfer data in a Forward Discrete Cosine Transformation stage.
FIG. 96 shows a memory management scheme for a method to transfer data in a Quantization stage.
FIG. 97 shows a memory management scheme for a method to transfer data in an Entropy Coding stage.
The following description and drawings are illustrative of the invention and are not to be construed as limiting the invention. Numerous specific details are described to provide a thorough understanding of the present invention. However, in certain instances, well known or conventional details are not described in order to not unnecessarily obscure the present invention in detail.
FIG. 1 shows an example of a typical computer system, which may be used with the present invention. Note that while FIG. 1 illustrates various components of a computer system, it is not intended to represent any particular architecture or manner of interconnecting the components as such details are not germane to the present invention. It will also be appreciated that network computers and other data processing systems which have fewer components or perhaps more components may also be used with the present invention. The computer system of FIG. 1 may, for example, be an Apple Macintosh computer.
As shown in FIG. 1, the computer system 1100, which is a form of a data processing system, includes a memory controller 1102 which is coupled to a host processor or processors 1101 and a host memory 1103 which may include a read only memory (ROM), volatile random access memory (RAM), and a nonvolatile memory. The host processor 101, is coupled to cache memory 1108 as shown in the example of FIG. 1. The core logic 1102 may also be coupled to the bus 1104. The bus 1104 interconnects the system to PCI peripheral components, such as a display controller and display device 1106 and to peripheral devices such as input/output (I/O) devices which may be mice, keyboards, modems, network interfaces, printers and other devices which are well known in the art. Typically, the input/output devices 1107 are coupled to the system through input/output controllers 1105. The bus 1104 may include one or more buses connected to each other through various bridges, controllers and/or adapters as is well known in the art. In one embodiment the I/O controller 1105 includes a USB (Universal Serial Bus) adapter for controlling USB peripherals.
FIG. 1 also shows a system core logic chip 1102 providing interfaces to the host processor 1101 and host memory 1103. The system core logic chip 1102 also acts as a bridge between the bus 1104 and the host processor 1101 and the host memory 1103. The system core logic 1102 is also known as a memory controller or a north bridge. A typical graphics controller 1106 receives graphics data from the host processor 1101 and the host memory 1103 through the system core logic 1102 and the bus 1104.
FIG. 2 shows another example of a typical computer system, which may be used with the present invention. The system 1200 of FIG. 2 includes a host processor or processors 1201 coupled to a system core logic 1202, a host memory 1203 coupled to the system core logic 1202. The bus 1204 interconnects these various components together and also interconnects these components 1201 and 1203 to a display controller and to peripheral devices such as input/output (I/O) devices 1207 through an I/O controller 1205. The bus 1204 may be a peripheral component interconnect (PCI) bus. A graphics controller 1206 is coupled to the system core logic 1202 through an interface such as accelerated graphics port (AGP) interface integrated with the system core logic 1202. The graphics controller 1206 is typically coupled to a display device 1211, such as a monitor or TV station. The graphics controller 1206 may be connected to an input of a video editing system.
The present invention in one embodiment integrates a media processor in a system core logic chip such as system core logic 1102 of FIG. 1 or 1202 of FIG. 2. The system core logic chip typically is memory controller and is referred to as a north bridge. FIG. 4B shows an example of one embodiment of the present invention. The system core logic 1410, which may be implemented as a single chip (integrated circuit) or multiple chips, includes a host interface 1414 coupled to the host processor 1411. The host interface 1414 provides accesses between the host processor 1411 and the logic 1410. The logic 1410 also includes a memory interface 1415 for controlling and accessing the host memory 1412 from the logic 1410. A media processor 1413 is integrated in the logic 1410. In one embodiment, this integration means that if logic 1410 is contained all on one chip (IC) then the media processor 1413 is on the same IC (e.g., same monolithic integrated circuit substrate). The logic 1410 also may include a PCI-0/AGP interface 1417. In one embodiment, the PCI-0/AGP interface may provide an interface to other external PCI devices. In another embodiment, the PCI-0/AGP interface 1417 may serve as an accelerated graphics port (AGP) coupled to an external graphics controller 1419. The graphics controller 1419 may be coupled to a display device 1425, such as a monitor or a TV station. The graphics controller 1419 may be coupled to an input of a video editing system. The logic 1410 may include a PCI-1 interface 1418. The PCI-1 interface may be coupled to another PCI device or it can be coupled to an input/output (I/O) controller 1420, also known as south bridge. Together, the north bridge and the south bridge may be referred to as a chipset. The I/O controller 1420 may provide as a bridge to other PCI buses which may connect more PCI devices, such as an Ethernet device, a modem, etc. In one embodiment, an IEEE-1394 bus 1421, also known as FireWire bus, may be coupled to the I/O controller 1420. In another embodiment, the FireWire bus 1421 may be directly coupled to the system core logic chip 1410 through PCI like interface. A bus 1416 interconnects all components together. In an alternative embodiment, the logic 1410 may include interfaces to many other components of the system, such as universal serial bus (USB), Ethernet device, etc. Other configurations may exist. One of the advantages of the present invention is that a media processor is built on a conventional system core logic chip which has more unused space. As a result, the cost of the system has been reduced, by combining a conventional system core logic with a media processor into a single-chip of a chipset.
As shown in FIG. 4B, in one embodiment, the media processor 1413 communicates with the host processor 1411 through the host interface 1414 and accesses the host memory 1412 through the memory interface 1415. The media processor 1413, in one embodiment, processes data autonomously and asynchronously to the host processor 1411. In another embodiment, the media processor 1413 communicates with the host processor 1411 through an interrupt mechanism. A software program executed by the host processor 1411 may control the interrupt mechanism. The media processor, in one embodiment, is capable of processing multiple media data streams simultaneously. Each media data stream may be a time related sequence of data representing related images (or audio data or both related image and audio data such as a motion picture). Thus, for example, a first image and a second image are related by a first time (e.g., the first image is shown 1 second, at normal playback speed, before the second image) and a third image and a fourth image are related by a second time (e.g., the third image is show, at normal play back speed, 2 seconds before the fourth image), and the third image is shown 1 second before the second image. It will be appreciated that these time durations (e.g., 1 second) are used for discussion purpose only that other times may be used. Often, information specifying such times is included in the media data stream which are processed by the media processor. Such media data streams may be referred to as time based media. Time based media include Quicktime movies and Quicktime streaming movies, and examples of time based media are provided in U.S. Pat. No. 6,134,243, which is hereby incorporated herein by reference.
FIG. 5B shows an example of one embodiment of a media processor of the present invention. The media processor 1510 can be used as the media processor 1413 of FIG. 4B. Referring to FIG. 5B, the media processor 1510 may contain multiple compute engines such as compute engine 1520. Multiple compute engines including compute engine 1520 are coupled to a chip interconnect 1519. The number of the compute engines is scalable and may be determined by the particular requirements for system performance versus chip size and cost. The media processor 1510 also includes a stream interface 1521 for gathering and distributing requests to and from the compute engine 1520 and the rest of the system.
The stream interface 1521 contains a memory mapping mechanism to convert linear logical addresses used by the compute engine 1520 to physical address for snooping and accessing memory. In one embodiment, the memory mapping mechanism contains a video address re-mapping table (VART) 1515, which is further described below, coupled to a memory management controller (MMC) 1516. The MMC 1516 receives a memory access request and determines whether such request needs to be mapped from a logical address to a physical address. If the memory request does not need to be mapped, the MMC 1516 will send the request to the coherent stream interface 1513 or the non-coherent stream interface 1514 directly. If the memory request needs to be mapped, the MMC 1516 will send the request to the VART 1515 for translation from logical addresses to physical addresses. The stream interface 1521 may also contain a compute engine to compute engine interface (not shown) providing accesses among the multiple compute engines.
One of the advantages of the media processor of one embodiment of the present invention is that both cache coherent and cache non-coherent interfaces are integrated in the single-chip north bridge which includes the media processor and the memory controller. This feature provides more flexibility over a conventional media processor. A conventional media processor normally uses mapped non-coherent memory access only. Cache non-coherent memory operations are those operations where data goes directly to and from memory and is returned directly back to the media processor and never goes through a processor cache. With cache non-coherent memory access, the data in the main memory may not be synchronized with those in the host processor's cache memory. A coherency between the host processor's cache memory and the main memory must be maintained (e.g., by software program), such that the data in the host processor's cache memory are synchronized with those in the main memory. On the other hand, a cache coherent memory system always goes through the host processor. The data of a cache coherent memory system may exist in the host processor's cache memory or in the host memory. Referring to FIG. 5B, when a coherent memory access request is issued, the host processor 1511 checks whether the host processor cache memory 1524 contains newer data than the host memory 1512. If the host processor cache 1524 has newer data, the host processor 1511 flushes its caches into the host memory 1512 before the data being read from the host memory 1512. With cache coherent memory system, the coherency between the host processor's cache memory 1524 and the host main memory 1512 is maintained by the host processor. However, cache coherent memory access is normally slower than cache non-coherent memory access. The present invention, in one embodiment, integrates both cache coherent and cache non-coherent interface for both memory accesses into the north bridge chip of the north/south bridge chipset, which provides great flexibility over a conventional design.
FIG. 6 shows a method used in an alternative embodiment of the present invention, such as the one shown in FIG. 4B. Referring to FIG. 6, the cache coherent interface receives a cache coherent access request in operation 1615, the cache coherent interface transmits the request to the host interface 1619. The host interface 1619 sends a cache coherency message to the host processor 1616. During the memory read access, the host processor 1616 checks whether its cache contains newer data than the host memory 1618. If the host processor's cache contains newer data than the host memory, the host processor flushes its cache to the host memory 1618. Then the cache coherent interface 1615 reads the data from the host processor's cache. During the memory write access, the cache coherent interface 1615 writes the data to the host memory 1618, thereafter, upon receiving the cache coherency message, the host processor 1616 refreshes its cache from the host memory 1618 to synchronize the data between its cache and the host memory. Upon receiving the cache coherency message, the host interface 1619 also snoops the request for cache coherency violations. If the violations occur, an error message will be generated through an interrupt mechanism.
The memory requests of FIG. 6 come from three sources: command queue fetch mode (CQM), instruction cache fill mode (ICM), and direct memory access (DMA) mode (DCM). The MMC 1516 of FIG. 5B may comprise a memory management control register (MMCR). In another embodiment, each compute engine such as compute engine 1520 of FIG. 5B comprises its own MMCR. The MMCR determines the type of the request sent to memory. FIG. 7 shows the layout of one embodiment of a MMCR. The MMCR 1700 contains 32 bits. The MMCR 1700 comprises three separate codes for each of the three sources of the memory requests. The CQM code 1701 occupies bit 23 to bit 25, the ICM code 1702 occupies bit 26 to bit 28, and DCM code 1703 occupies bit 29 to bit 31. These codes specify whether the request is mapped/unmapped and coherent/non-coherent, as described in table 1704. In an alternative embodiment, bit 0 of the logical address may specify whether the request is mapped/unmapped and coherent/non-coherent. For mapped addresses the fields in the VART table entry may determine if the access is coherent or non-coherent. The host processor such as host processor 1511 of FIG. 5B updates the MMCR through a memory mapped address such as memory mapped registers 1523, through the master interface 1522 of FIG. 5B. The fields of the MMCR are initially undefined; they must be loaded before a memory access can occur.
The memory mapping mechanism of FIG. 5B also determines attributes to control cache coherency. As shown in FIG. 5B, the stream interface 1521 also contains a coherent stream (CS) interface 1513 and a non-coherent stream (NCS) interface 1514. For the CS interface, requests are sent to the host processor 1511 to be snooped by the host processor's caches. CS requests are used for memory data that may reside in the host processor's caches or the data that may reside in the targeted memory mapped addresses. NCS requests are sent directly to the host memory 1512 and are used for data requests that require high bandwidth. Such coherency is maintained through software. Thus, the software is responsible for synchronizing the host caches and the host memory. The stream interface 1521 may also include a master interface 1522. The master interface 1522 provides the host processor 1511 with the ability to control the operation of the compute engine 1520. In one embodiment, the host processor 1511 controls the operation of the compute engine 1520 through a set of memory mapped registers 1523. Among other things, these memory mapped registers 1523 define a command queue, which is described further below, from which commands or routines are sent to the compute engine 1520, MMCR as described above and various interrupt control mechanisms.
Memory access requests from compute engines are labeled as being mapped or unmapped. Unmapped requests are also labeled as being coherent or non-coherent. Mapped requests undergo a mapping from their linear logical address provided by the compute engine, such as compute engine 1806 of FIG. 8. The mapping also determines if the request is coherent or non-coherent, which is described further below. Referring to FIG. 8, a mapped request from the compute engine 1806 is sent to a video address re-mapping table (VART) 1805 for translation from a linear logical address to a physical address. The VART 1805 then determines whether the request is coherent, if so, the VART 1805 sends the request to the coherent interface 1803 and then out to the host processor 1801. If the request is non-coherent, the VART 1805 sends the request to non-coherent interface 1804 and then out to the host memory 1802. Coherent and non-coherent interfaces and the VART are part of the stream interface 1807.
In a modem computer system, two address spaces are present. The logical address space and the physical address space. The logical address space is the address space accessed by the software running on the host and there is a logical address space accessed by the software running at the video stream processor (VSP) such as the media processor 1510. The physical address space is a set of address ranges occupied by the system hardware devices and system memory. The address re-mapping tables provide the mapping between the logical addresses used by the software in order to access physical devices at their physical addresses. VART is the table that maps logical addresses used by the VSP engine to the physical addresses of the main memory and other system devices.
In one embodiment of the invention, the tables are located in the main memory and addressed by their physical address without any address translation. Different devices may access the same physical location using different logical address, provided that these logical addresses are mapped to the same physical space by a re-mapping table. It may be possible for VSP engine to directly access other physical devices, such as AGP or PCI devices, when the proper mapping is provided by the VART. The memory management software which is part of the operating system (OS) kernel software is responsible for allocating physical memory, assigning to some logical addresses and storing the mapping information in the address re-mapping tables. For the VSP devices, the physical memory regions must be allocated and mapped to logical addresses prior to any VSP command execution that will access that memory regions. The system software sets up the VART entries accordingly. The memory mapping should stay valid until the command execution is completed. When the shared memory ranges are no longer needed by the VSP, the host or other devices, the physical memory may be freed and the corresponding VART entries are invalidated. Pages are the usual mechanism used for addressing information in a memory system. An example of logical to physical address mapping from a VSP is described further below.
The video address mapping table (VART) is made up of table entries. Each table entry corresponds to a logical page in the address space assigned to the media processor. The table entry contains information about the corresponding physical memory page number as well as if the memory access is cache coherent. The system software is responsible for maintaining VART, whether a page is allocated for use by the media processor, the system software creates a corresponding entry in the VART, and marks it as valid. When the page is freed, the VART entry is marked invalid.
Physical addresses are allocated in pages (e.g., each page has 4096 bytes). Pages are the usual mechanism used for addressing information in a logical memory system. Pages are numbered and both physical and logical addresses often include a page number and an offset into the page. As an example, referring to FIG. 11, the VART 2107 contains entries that include the addresses of pages i, j, and k. Each VART page in the logical address space has a corresponding page in physical memory space. For example, VART page 2104 has a corresponding physical page 2110. In this example, the VART 2107 contains valid entries for mapping pages i 2104, page j 2105, and page k 2106 in the logical address space into corresponding physical page i 2110, page j 2109, and page k 2111 respectively. When a request for mapping is received, the logical page frame number (LPN) will be extracted from a logical address of address space 2101. The VART entry corresponding to the LPN will be extracted. If a valid entry is found, the PPN will be extracted and the physical address will be determined and the logical address is mapped to a physical address.
One of the advantages of the VART 2107 in the present invention is that the video device address space can be overlapped the logical address space 2101. Such video device address space can be shared by other devices, or the host processor such as host processor 1511 of FIG. 5B. On the other hand, a conventional graphics controller coupled to an accelerated graphics port (AGP) has its own dedicated address space. In general, such address space is allocated by the software during the boot time of the system. Such address space cannot be used by any other components of the system. System software indicates the access to the corresponding physical memory by different devices. If the video stream processor (VSP) address space overlaps the system address space, only one address may need to be allocated. On the other hand, if the address spaces are disjoint, the system software may use two logical addresses to access some logical page of physical memory. As a result, such address space cannot be used by others, even though the AGP graphics device is not using them. This limitation posts an inconvenience to the memory management, as well as the cost of the memory bandwidth of the host system.
A conventional graphics address re-mapping table (GART), such as GART 2108 can only map a dedicated graphics accelerator address space such as AGP device address space 2114. Unlike GART, the VART of the present invention can map a logical address space located almost anywhere in the logical address space 2101. In an alternative embodiment of a system of the invention, the system includes a VART in addition to a GART and host maintained tables. In fact, in one embodiment, the video device address space 2103 can be the same range as the AGP device address space 2114. This advantage provides more flexibilities and bandwidth to the system.
When a media processor of the present invention processes multiple media data, the application software or the system software is responsible to allocate enough memory resources for the processing. In one embodiment, a large block of memory may be pre-allocated before any data processing occurs. In another embodiment, the memory allocation may be performed dynamically as needed. When a page is allocated for use by VSP, the system software updates the VART entry corresponding to the LPN of its logical address with the PPN of the newly allocated physical memory page. After processing the media data, if the physical memory page is no longer needed, the physical memory page is released back to the main memory and the corresponding entry of the VART is marked invalid.
The VART normally comprises a VART base register (VARTBASE) and a VART size register (VARTSIZE). FIG. 9 shows an embodiment of a VART entry, as well as VARTBASE and VARTSIZE. Referring to FIG. 9, VARTBASE 1906 defines the location of the VART and the VARTSIZE 1907 defines how big the VART is in 64-bit words. Both VARTBASE and VARTSIZE comprise 19-bit data. In one embodiment, VARTBASE occupies from bit 0 to bit 19 and VARTSIZE occupies from bit 13 to bit 31. Each VART entry maps two 4K-Byte pages, including an even page 1901 and an odd page 1902. Each entry of even or odd page contains a physical page frame number (PPN), which occupies from bit 0 to bit 19. The entry also contains a coherent bit (C-bit), which indicates whether the mapping is coherent access. A logical value of one indicates the mapping is coherent. The entry further contains a valid bit (V-bit) indicating whether the entry is valid. A logical value of one indicates the entry is valid. The V-bit is initially set to invalid (e.g., logical value of zero), until a physical memory page is allocated and the VART is updated. These bits may be set by a software program that allocates the pages.
A logical address (LA) that needs to be mapped contains a logical page frame number (LPN) and an offset. A typical LPN has 19 bits, from bit 0 to bit 18. Bit 20 to bit 31 are the offset of the logical address. Before a mapping takes place, the LPN will be compared with the VARTSIZE register to determine if the request is out of boundary of the VART. If the request does not fit in the VART, a VAR