Source: http://www.google.com/patents/US20020138678?dq=552685
Timestamp: 2015-02-01 01:25:42
Document Index: 147618188

Matched Legal Cases: ['ART) 552', 'ART 552', 'ART 442', 'art 1300', 'art 1400', 'art 1500']

Patent US20020138678 - System on a chip having system bus, external bus, and bus arbiter with ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA system on a chip has functional blocks accommodated by at least one system bus, and an external bus for accommodating communication with external blocks. A single multi-jurisdictional bus arbiter has programmable rankings for assigning priorities to requests from blocks that are masters for either...http://www.google.com/patents/US20020138678?utm_source=gb-gplus-sharePatent US20020138678 - System on a chip having system bus, external bus, and bus arbiter with programmable priorities for both buses. software, and method for assigning programmable prioritiesAdvanced Patent SearchPublication numberUS20020138678 A1Publication typeApplicationApplication numberUS 09/773,874Publication dateSep 26, 2002Filing dateJan 31, 2001Priority dateJan 31, 2001Also published asDE10152970A1, DE10152970B4, US6976108Publication number09773874, 773874, US 2002/0138678 A1, US 2002/138678 A1, US 20020138678 A1, US 20020138678A1, US 2002138678 A1, US 2002138678A1, US-A1-20020138678, US-A1-2002138678, US2002/0138678A1, US2002/138678A1, US20020138678 A1, US20020138678A1, US2002138678 A1, US2002138678A1InventorsYoungsik Kim, Yun-Tae LeeOriginal AssigneeYoungsik Kim, Yun-Tae LeeExport CitationBiBTeX, EndNote, RefManReferenced by (8), Classifications (6), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetSystem on a chip having system bus, external bus, and bus arbiter with programmable priorities for both buses. software, and method for assigning programmable prioritiesUS 20020138678 A1Abstract A system on a chip has functional blocks accommodated by at least one system bus, and an external bus for accommodating communication with external blocks. A single multi-jurisdictional bus arbiter has programmable rankings for assigning priorities to requests from blocks that are masters for either one of the both buses. Software and methods are also provided for assigning the priorities. The requests are analyzed with respect to which of the buses they require, and then priorities are assigned to maximize bus utilization, with increased speed for a system on a chip. In addition, a multi-jurisdictional multi-channel direct memory access block can be a master block for the system bus or the external bus. Images(17) Claims(35)
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT(S) [0074] As has been mentioned, the present invention provides a system on a chip. Various embodiments of the invention are now described with reference to FIG. 4, FIG. 5, FIG. 6. It will be appreciated that aspects of these embodiments may be rather similar to each other, sharing many similar blocks that are similarly numbered. [0075] Referring now particularly to FIG. 4 a system 400 is provided on a chip 405, according to an embodiment of the invention. System 400 includes a system bus 410, that can be an advanced microcontroller bus architecture (AMBA) bus developed, for example, by Advanced RISC Machines (ARM) Co. System bus 410 can be made by a advanced high performance bus (AHB). [0076] System-on-a-chip 400 includes a CPU 422, that is a master of system bus 410. CPU 422 may be an ARM reduced instruction set computer (RISC) CPU with a cache. Exemplary blocks for CPU 422 may be parts designated by ARM Co. as ARM920T and ARM940T. [0077] System-on-a-chip 400 also includes DDMA blocks 424, 426, directly connected to respective IP blocks 434, 436. Each of IP blocks 434, 436 may be an Ethernet medium access control (MAC), or a peripheral component interconnect (PCI) bridge. System 400 moreover includes an internal memory controller 462 for accessing an internal memory 472. [0078] Another block of system 400 is a special GDMA block 430, that is also called a multi-jurisdictional multi-channel General DMA (mJnCGDMA) block 430 according to the invention, which is also known as simply GDMA 430. It can be for n-channels, as indicated by the overall design. [0079] Moreover, a special multi-input external memory controller 440 is provided according to an embodiment of the invention for the SOC 400. [0080] System 400 additionally includes an external bus 415, which is for accessing off-chip blocks. External bus 415 is coupled with the multi-input external memory controller 440. [0081] In other words, multi-input external memory controller 440 is a block that is coupled to both the system bus 410 and to external bus 415. For purposes of this document, that renders block 440 a �dual� block. [0082] Another aspect of controller 440 is that receives inputs from the above described block 430 directly, through a so-called third path 431, as will be described in more detail below. Third path 431 is distinct from the system bus 410 and the external bus 415. [0083] System 400 further includes a DRAM Refresh Controller 464, which is coupled with the multi-input external memory controller 440. [0084] Off-chip blocks for use with system 400 can be an external device 473, an external Input/Output device 474, a ROM 482, a DRAM 484, a static RAM (SRAM) (not shown), a flash memory (not shown), etc. External device 473 uses external bus 415 when it is not used by the functional blocks within the SOC 400. (For the functional blocks within the SOC 400 to use external bus 415, a control by the multi-input external memory controller 440 is necessarily required.) System 400 importantly includes a special multi-jurisdictional arbiter 495 for managing requests affecting both the system bus 410 and the external bus 415. Software, methods and schemes for arbiter 495 are presented below in more detail. At this point it is sufficient to note that the present invention's mJmCGDMA block 430 can be a master for both the system bus 410 and the external bus 415. This is accomplished with the cooperation of the present invention's multi-input external memory controller 440, which receives inputs also from mJmCGDMA 430 to that effect. [0085] Referring now particularly to FIG. 5 a system 500 is provided on a chip 505, according to another embodiment of the invention. The discussion is the same as with FIG. 4 for system bus 410, external bus 415, CPU 422, DDMA#0 424, DDMA#N 426, IP#0 434, IP#N 436, mJmCGDMA 430, multi-input external memory controller 440, internal memory controller 462 and internal memory 472, all of which are provided on chip 505. In addition, system 500 is adapted for working, through external bus 415, with off-chip blocks such as external device 473, External I/O 474, ROM 482, DRAM 484, etc., similarly as discussed above in connection with FIG. 4. [0086] In the embodiment of FIG. 5, more components are provided on chip 505 than on chip 405 of FIG. 4. An additional, auxiliary system bus APB 516, such as an advanced peripheral bus, is connected to main system bus 410 through a main bridge block 518, such as an APB Bridge. Auxiliary system bus APB 516 is for accessing additional functional blocks, configured as its slaves. Main bridge 518 may be configured as a slave to main system bus 410, for accessing additional functional blocks coupled with auxiliary system bus APB 516. [0087] Additional functional blocks accessible through auxiliary system bus APB 516 may include a universal asynchronous receiver-transmitter (UART) 552, a universal serial bus (USB) 554, a timer 556, and an interrupt controller 558. [0088] System 500 moreover includes a multi-jurisdictional arbiter 595 for managing requests affecting both the system bus 410 and the external bus 415. Arbiter 595 is optionally adapted to manage requests also from blocks connected through auxiliary system bus APB 516. [0089] Referring now particularly to FIG. 6 a system 600 is provided on a chip 605, according to yet another embodiment of the invention. The discussion is the same as with FIG. 5 for external bus 415, CPU 422, DDMA#0 424, DDMA#N 426, IP#0 434, IP#N 436, mJmCGDMA 430, multi-input external memory controller 440, internal memory controller 462 and internal memory 472, auxiliary system bus APB 516, main bridge block 518, UART 552, USB 554, timer 556, and interrupt controller 558, all of which are provided on chip 605. In addition, system 600 is adapted for working, through external bus 415, with off-chip blocks such as external device 473, External I/O 474, ROM 482, DRAM 484, etc., similarly as discussed above. [0090] An important difference is that a main system bus is implemented by two buses, a left system bus AHBL 610-L and a right system bus AHBR 610-R. These are divided by a bus switch 612, implemented by a suitable bridge. [0091] System 600 moreover includes a multi-jurisdictional arbiter 695 for managing requests affecting both the left system bus 610-L and the right system bus 610-R, along with the external bus 415. This is accomplished also by arbiter 695 having a direct line to bus switch 612. Arbiter 695 is optionally adapted to also manage requests from blocks connected through auxiliary system bus APB 516. [0092] In all three shown embodiments, the arbiter can handle, as may be desired, the master blocks of all buses on a non-hierarchical form. Alternately, it may treat some of them hierarchically with respect to others. [0093] Referring now to FIG. 7, a block diagram is shown for a multi-jurisdictional bus arbiter 495 according to an embodiment of the present invention. It will be appreciated that, although the description is that for arbiter 495 of FIG. 4, the description is applicable also to arbiter 595 and 695, with minimal adjustments. It will also be observed that, given the level of detail of FIG. 7, system bus 410 is shown split into its two components of address and control 410-C and data 410-D. [0094] Arbiter 495 includes a request decoder 710. Request decoder 710 is adapted to receive request signals REQ from the on-chip blocks that operate as masters of system bus 410, and also from the off-chip blocks that operate as masters of external bus 415. The request signals REQ are received as digital signals, and decoded by request decoder 710, which in turn produces a pertinent output. Sometimes the request signals from the masters of system bus 410 are designated as SREQ, and the request signals from the masters of external bus 415 are designated as EREQ. [0095] Arbiter 495 also includes a priority scheduler 720. Priority scheduler 720 is adapted to receive the output of request decoder 710. Priority scheduler 720 then decides the relative priorities of the all the master block(s), as is described below. It should be remembered that priority scheduler 720 of the invention is optionally capable of being programmed with different programs, which would implement different schedules. It is advantageous, but not necessary, that the program for selecting priorities reside in priority scheduler 720. [0096] Once the priorities have been decided, priority scheduler 720 outputs signals indicating which master block has the top priority. A key part of the invention is that a top priority can be determined to be for an off-chip block at the same time as for an on-chip block. [0097] The output of priority scheduler may optionally be fed back into request decoder 710, if the requests are stored there. Equivalently, the requests can be stored into priority scheduler 720, and be read from it. [0098] Arbiter 495 additionally includes a system bus master selector 730. Master selector 730 is adapted to receive an output of priority scheduler 720 (or equivalently, of request decoder 710, if the requests are stored there). Master selector 730 is further adapted to transmit a grant signal GNT to the system bus master block that has the top priority, responsive to the received output of the priority scheduler. Since this grant signal is for a master block of system bus 410, it is also designated as SGNT. [0099] Arbiter 495 moreover includes a system bus slave selector 740. System bus slave selector 740 is adapted to receive a corresponding signal CRS from system bus master selector 730, the content of which has originated from priority scheduler 720 (or equivalently, of request decoder 710, if the requests are stored there). Equivalently, corresponding signal CRS could be received directly from priority scheduler 720. In addition, system bus slave selector 740 is optionally adapted to receive an output of the system bus 410. System bus slave selector 740 is adapted to transmit a select signal SEL to one of the system bus slaves. In some embodiments, external memory controller 440 is such a system bus slave. [0100] Arbiter 495 further includes an external bus master selector 750. External bus master selector 750 is adapted to receive another output of priority scheduler 720 (or equivalently, of request decoder 710, if the requests are stored there). External bus master selector 750 is further adapted to transmit another grant signal GNT to the external bus master block that has the top priority, responsive to the received output of the priority scheduler. Since this grant signal is for a master block of external bus 415, it is also designated as EGNT. External bus master selector 750 is further adapted to transmit a drive signal EDR to external memory controller 440. [0101] Referring now to FIG. 8, a multi-input external memory controller 440 is described. It will become apparent that controller 440 may be used with the bus arbiter of FIG. 7, and any of its variations suggested above. It will also be observed that, given the level of detail of FIG. 7, external bus 415 is shown split into its two components of address and control 415-C and data 415-D. [0102] Multi-input external memory controller 440 includes an external bus controller 810. External bus controller 810 is adapted to control the external bus 415. [0103] Optionally and preferably, external bus controller 810 is adapted to receive inputs directly from the arbiter 495. More specifically, it can receive a select signal SEL from system bus slave selector 740. Alternately, it can receive an external bus grant signal EGNT from external bus master selector 750. [0104] External memory controller 440 also includes an address and control multiplexer 820. Address and control multiplexer 820 is adapted to receive address and control inputs from both system bus 410 and the multi-jurisdictional multi-channel general direct memory access (mJmCGDMA) block 430. Address and control multiplexer 820 is further adapted to transfer one of the received address and control inputs to external bus controller 810. [0105] External memory controller 440 additionally includes a write data multiplexer 830. Write data multiplexer 830 is adapted to receive data inputs from both the system bus 410 and the mJmCGDMA block 430. Write data multiplexer 830 is further adapted to transfer one of the received data inputs to the external bus controller 810. [0106] External memory controller 440 moreover includes a read data demultiplexer 840. Read data demultiplexer 840 is adapted to receive data inputs from the external bus controller 810. Read data demultiplexer 840 is further adapted to transfer the received data inputs to one of the system bus 410 and the mJmCGDMA block 430. [0107] In the preferred embodiment, all of the address and control multiplexer 820, write data multiplexer 830, and read data demultiplexer 840 are controlled by inputs from external bus controller 810. [0108] External memory controller 440 optionally additionally includes three tri-state buffers 852, 854, 856 coupled between external bus controller 810 and external bus 415. These may be controlled by external bus controller 810. [0109] Referring now to FIG. 5 operations of system 500 are described. A person skilled in the art will discern how the following descriptions are adaptable also for systems 400 and 600 of FIG. 4 and FIG. 6, respectively. [0110] First operations of CPU 422 are described. The person skilled in the art will discern that explanations for remaining ones of the components may be derived from the accompanying drawings. [0111] When CPU 422 issues a system bus request to obtain a grant of system bus 410 ownership, CPU 422 can read data from, or write data to, registers of the blocks coupled with system bus 410. Furthermore, after having been granted ownership of system bus 410 and the auxiliary main bus 516, CPU 422 can read data from, or write data to, registers of the blocks connected through main bridge 518. For access to external DRAM 484, CPU 422 needs to obtain ownership of both system bus 410 and external bus 415. To accomplish this, CPU 422 first accesses the multi-input external memory controller 440 through the system bus 410, and then controller 440 can read and write data between the CPU and the DRAM 484 through also the external bus 415. Thus, CPU 422 operates as a system bus master. Same for CPU 422 accessing ROM 482. [0112] DDMA blocks 424, 426 perform read and write operations on data stored in the internal memory 472 or the external memory 482. The first operation requires ownership of only system bus 410, while the latter operation requires ownership of both system bus 410 and external bus 415. Thus, DDMA blocks 424, 426 operate as system bus masters. [0113] Multi-jurisdiction, multi-channel GDMA block 430 performs read and write operations on data stored in internal memory 472 or external memory 484. Operations of the GDMA block 430 are classified into data communication of four types: [0114] a) between a programmed arbitrary IP block and internal memory 472, [0115] b) between an arbitrary IP block and external memory 484, [0116] c) between internal memory 472 and external memory 484, and [0117] d) between the external memories 482 and 484. [0118] The multiple channels can program each of all four types of data communication within the GDMA block 430. Even during programming of multiple channels, the GDMA block 430 performs a control such that only one channel operates at one time. The exemplary arbitrary IP blocks to be programmed in each of the GDMA multiple channels may include UART 442, USB 554, interrupt controller 558, etc. [0119] Of the above described types of data communication, a) requires bus ownership of only system bus 410, b) and c) require ownership of both system bus 410 and external bus 415, and d) one require bus ownership of only external bus 415. Thus, multi-jurisdiction, multi-channel GDMA 430 may operate either as an external bus master during the fourth type of operation, or as a system bus master during the remaining types of operations. [0120] DRAM refresh controller 464, which is one of the masters of external bus 415, does not need system bus ownership. It uses only external bus 415 in order to generate periodically a signal for refreshing external DRAM 484. In order for DRAM refresh controller 464 to use external bus 415, external memory controller 440 is used to transmit a signal to the outside of the chip through external bus 415, in which case the system bus masters cannot use external memory controller 440 or external bus 415. In the same manner, for use of external bus 415 by a system bus master, a signal is transmitted to the outside of the chip by a control of external memory controller 440, while the external bus masters cannot use external bus 415 during that time. [0121] The above type of description can be extended to any on-chip block or off chip block, depending on known and anticipated operation characteristics of each functional block. After such descriptions are complete, it is found advantageous to discuss what type of signals would be used for implementation of a device according to the invention. [0122] The type of bus ownership requests may be represented by four two-bit bus request signals REQ[1:0]={EREQ, SREQ} using a 1-bit system bus request signal SREQ and a 1-bit external bus request signal EREQ. That is, if REQ[1:0]=2′b00, no request for a bus is made (no request), and if REQ[1:0]=2′b01, a request for system bus 410 only is made (system bus only request). If REQ[1:0]=2′b10, a request for external bus 415 only is made (external bus only request), and if REQ[1:0]=2′b11, a request for both buses is made (both bus request). [0123] Similarly, a bus ownership grant may be represented by a bus ownership grant signal GNT[1:0]={EGNT, SGNT}. That is, if GNT[1:0]=2′b00, no bus is granted (no grant), and if GNT[1:0]=2′b01, system bus 410 only is granted (system bus only grant). If GNT[1:0]=2′b10, external bus 415 only is granted (external bus only grant), and if GNTt[1:0]=2′b11, ownership of both buses concurrently is granted (both bus grant). [0124] An important aspect of the invention is to classify requests with reference to which bus they would use, and which they would leave idle. Classification may advantageously be implemented in the coding of the above described signals. [0125] Referring now to FIG. 9, a Table 1 is shown that classifies the possible type of bus requests by each functional block. As shown in Table 1, external bus masters are DRAM refresh controller 464, a channel of mJmCGDMA block 430, and external device 473. These submit a bus request signal REQ=2′b10. System bus masters are CPU 422, DDMA blocks 424, 426, and the channel of GDMA 430 submitting a bus request signal REQ=2′b01 or REQ=2′b11. [0126] Referring now to FIG. 10, a diagram is shown for further conceptualizing the characteristics of the requests. This type of diagram is also known as a Venn diagram. Set S is for grouping together, bundling or classifying the requests of system bus 410. Set E is for the requests of external bus 415. Their section (subset ES) is for those requests that require both buses. Subset ES leaves, in set S, a subset SO for System bus Only requests, and in set E a subset EO for External bus Only requests. The union of E and S (EO+ES+SO) is given by A, and contains All the requests. In more rigorous mathematical notation, assuming that Function n(X) is defined as the number of elements of set X, the relationship is that n(A)=n(E∪S)=n(EO)+n(ES)+n(SO) and n(ES)=n(E∩S)=n(E∩S)=n(S∩S). [0127] Referring now to FIG. 11, it is further advantageous to show the requests of FIG. 9 in the sets indicated by FIG. 10. First, the set of functional blocks making a system bus request by a bus request signal REQ[1:0] equal to 2′b01 or 2′b11, is defined as set S which is the same as the set of system bus masters. Second, the set of functional blocks making an external bus request by a bus request signal REQ[1:0] equal to 2′b10 or 2′b11 is defined as set E. Third, the set of functional blocks making only a system bus request through a bus request signal REQ[1:0] equal to 2′b01 is defined as set SO. Fourth, the set of functional blocks making only an external bus request through a bus request signal REQ[1:0] equal to 2′b10 is defined as set EO which is the same as the set of external bus masters. Fifth, the set of functional blocks making a request for both system bus and external bus through a bus request signal REQ[1:0] equal to 2′b11 is defined as set ES. Sixth, the set of functional blocks making a request for a system bus or an external bus through a bus request signal REQ[1:0] equal to 2b′01, 2′b10 or 2′b11 is defined as set A. [0128] The above discussion facilitates description of the operation of special components of the invention. [0129] Referring again to FIG. 7 operations of arbiter 495 are described for enabling the above types of requests. The operations are described according to the classifications of FIG. 11. The methods of arbiter 495 for assigning priorities, however, is described later. [0130] First, if the selected functional block is the element of set ES (a bus request signal REQ is 2′b11), only system bus master selector 730 is driven. It grants a system bus grant signal SGNT 11 to the selected functional block. The system bus master selector 730 also drives the system bus slave selector 740. The system bus slave selector 740 optionally also drives external memory controller 440, so that the system bus master functional block that is being granted the bus ownership request may be granted usage of external bus 415 as well. In this case, external memory controller 440 receives system bus address and control signal S 16 via address and control portion 410-C of system bus 410 from the selected master block. External memory controller 440 also receives system bus data S17 via data portion 410-D of the system bus 410 from the selected master block. The received address & control signal S16, and data S17 are for connecting to an external bus. [0131] On the other hand, if the bus request signal is 2′b01 or 2′b10, the system bus master selector 730 and the external bus master selector 750, respectively, select different functional blocks that are granted bus grant signals. [0132] In other words, if the selected functional block is an element of set EO (the bus request signal REQ is 2′b10), then the system bus master selector 730 may further select a functional block which is one of the elements of set SO. That is, if there are functional blocks that have made requests which belong to the set SO among the remaining functional blocks (excluding the firstly selected functional block), the functional block having the highest priority among those functional blocks is then selected. The external bus master selector 750 is driven so that an external bus grant signal EGNT is transmitted to the firstly selected functional block, while the system bus master selector 730 is driven so that a system bus grant signal SGNT is transmitted to the secondly selected functional block. The external bus master selector 750 transmits a drive signal EDR to drive the external memory controller 440, so that the selected external bus master may use the external bus 415. The system bus master selector 730 drives the system bus slave selector 740 to select a system bus slave depending on the operation of the selected system bus master. The system bus slave selector 740 determines which bus slave can be used from the system bus address and control signal S 18, to transmit a selection signal to the selected bus slave. [0133] Third, if the selected functional block is the element of set SO, request decoder 710 may further select one functional block in set EO. That is, if there are functional blocks that belong to the set EO among the remaining functional blocks (excluding the firstly selected functional block), the functional block having the highest priority among those functional blocks is then selected. System bus master selector 730 is driven so that the system bus grant signal SGNT is transmitted to the firstly selected functional block, while the external bus master selector 750 is driven so that the external bus grant signal EGNT is transmitted to the secondly selected functional block. The external bus master selector 750 drives the external memory controller 440 so that the selected external bus master may use the external bus 415. [0134] Referring again to FIG. 8, operations of multi-input external memory controller 440 are described for enabling the above types of requests. The operations are described according to the classifications of FIG. 11. [0135] When the external memory controller 440 operates as a system bus slave, a system bus master operates as the element of set ES such that it may use system bus 410 and external bus 415 at the same time. In this case, the system bus slave selector 740 sends a signal SEL driving external memory controller 440 to operate as a system bus slave, while the external bus master selector 750 does not drive the external memory controller. Then, the external bus controller 810 sends a control signal S38 to the address and control multiplexer 820, the write data multiplexer 830, and the read data demultiplexer 840. After that, the external bus controller 810 receives address and control signal S16 and data S17 via system bus 410 from the system bus master functional block, and decodes them to drive external bus 415 so as to access a memory or an I/O device outside the chip. For this purpose, the external bus controller 810 sends a control signal S39 to drive the tri-state buffers 852, 854 and 856 into an active state. That is, when CPU 422 or DDMA block 424 makes requests for both system bus 410 and external bus 415, the external memory controller 440 receives the address and control S16 and the data S17 from the system bus 410 and drives external bus 415. [0136] On the other hand, when the external memory controller 440 does not operate as a system bus slave, but is driven by the external bus master selector 750 by a drive signal EDR, external memory controller 440 controls external bus 415 so that an external bus master may use external bus 415. The external bus master may be DRAM refresh controller 464, a channel of mJmCGDMA 430, or external device 473. External bus master selector 750 informs the external bus controller 810 of this by the drive signal EDR. [0137] If the DRAM refresh controller is selected among external bus masters, external bus controller 810 cuts off signals from address and control multiplexer 820, write data multiplexer 830, and read data demultiplexer 840, and instead generates and sends a control signal for refreshing DRAM 484. If external device 473 is selected, external bus controller 810 cuts off signals from address and control multiplexer 820, write data multiplexer 830, and read data demultiplexer 840, and sends control signal S39 to tri-state buffers 852, 854, and 856 to place them in a high-impedance state, so that external device 473 can drive external bus 415. After the channel of GDMA 430 is granted external bus ownership for data communication between external memories (bus request signal REQ=2′b10), the external memory controller 440 receives address, control signal, and data S15 directly from the GDMA channel, to thereby drive external bus 415, instead of receiving address and control signal S16 and data S17 from system bus 410. To this end, the external bus controller 810 may be in direct communication with the GDMA channel through the control signal S38 from address and control multiplexer 820, write data multiplexer 830, and read data demultiplexer 840. [0138] The signals exchanged between GDMA 430 and address and control multiplexer 820, write data multiplexer 830, and read data demultiplexer 840 are through lines of the third path 431 shown in FIG. 4. [0139] The invention additionally provides methods, which are described below. Moreover, the invention provides apparatus that performs, or assists in performing the methods of the invention. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored in the computer. The methods and algorithms presented herein are not necessarily inherently related to any particular computer or other apparatus. In particular, various general-purpose machines may be used with programs in accordance with the teachings herein, or it may prove more convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these machines will appear from this description. [0140] Useful machines or articles for performing the operations of the present invention include general-purpose digital computers or other similar devices. In all cases, there should be borne in mind the distinction between the method of operating a computer and the method of computation itself. The present invention relates also to method steps for operating a computer and for processing electrical or other physical signals to generate other desired physical signals. [0141] The invention additionally provides a program, and a method of operation of the program. The program is most advantageously implemented as a program for a computing machine, such as a general purpose computer, a special purpose computer, a microprocessor, etc. [0142] The invention also provides a storage medium that has the program of the invention stored thereon. The storage medium is a computer-readable medium, such as a memory, and is read by the computing machine mentioned above. [0143] A program is generally defined as a sequence of steps leading to a desired result. These steps, also known as instructions, are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated or processed. When stored, they can be stored in any computer-readable medium. It is convenient at times, principally for reasons of common usage, to refer to these signals as bits, data bits, samples, values, elements, symbols, characters, images, terms, numbers, or the like. It should be borne in mind, however, that all of these and similar terms are associated with the appropriate physical quantities, and that these terms are merely convenient labels applied to these physical quantities. [0144] This detailed description is presented largely in terms of flowcharts, display images, algorithms, and symbolic representations of operations of data bits within a computer readable medium, such as a memory. Such descriptions and representations are the type of convenient labels used by those skilled in programming and/or the data processing arts to effectively convey the substance of their work to others skilled in the art. A person skilled in the art of programming can use this description to readily generate specific instructions for implementing a program according to the present invention. For the sake of economy, however, flowcharts used to describe methods of the invention are not repeated in this document for describing software according to the invention. [0145] Often, for the sake of convenience only, it is preferred to implement and describe a program as various interconnected distinct software modules or features, collectively also known as software. This is not necessary, however, and there may be cases where modules are equivalently aggregated into a single program with unclear boundaries. In any event, the software modules or features of the present invention can be implemented by themselves, or in combination with others. Even though it is said that the program can be stored in a computer-readable medium, it should be clear to a person skilled in the art that it need not be a single memory, or even a single machine. Various portions, modules or features of it can reside in separate memories, or even separate machines. The separate machines may be connected directly, or through a network, such as a local access network (LAN), or a global network, such as the Internet. [0146] In the present case, methods of the invention are implemented by machine operations. In other words, embodiments of the program of the invention are made such that they perform methods of the invention that are described in this document. These can be optionally performed in conjunction with one or more human operators performing some, but not all of them. As per the above, the users need not be collocated with each other, but each only with a machine that houses a portion of the program. Alternately, some of these machines can operate automatically, without users and/or independently from each other. [0147] Referring now to FIG. 12, a diagram is first provided for visualizing in part rankings for methods that are subsequently described according to an embodiment of the invention. It should be remembered that the rankings of FIG. 12 are only one example, and other rankings are possible according to the invention. [0148] According to the hybrid arbitration method, requests 422-1, 424-1, 426-1, 428-1, 428-2, 428-3, 428-4, 464-1 are first bundled in groups according to the master blocks that originate them. Each group contains requests of equivalent importance. Request 464-1 from DRAM 464 is placed in Group E by itself. Requests 424-1, 426-1, 428-1, 428-2, 428-3, 428-4 are bundled in Group G, from the DDMA blocks 424, 426, and four channels of GDMA 430, respectively. And request 422-1 from CPU 422 is placed in Group H by itself. to Then the groups are ranked according to their importance. Group E (request to refresh DRAM) is ranked as the most important, and Group G and Group H are bundled in a composite Group F as being equivalent. [0149] It should be noted that in the scheme of FIG. 12 there is only one diagram, for addressing requests of both the internal bus and the external bus for a single arbiter 495. In addition (not depicted) is the fact that requests are also classified based on which of the two buses they would use. [0150] Methods of the invention are now described. [0151] Referring now to FIG. 13, a flowchart 1300 is used to illustrate a general method according to an embodiment of the invention. [0152] According to a step 1310, any additional requests are input in arbiter 495. This usually happens once for every cycle of operation. [0153] According to a next step 1320, the inputted requests are characterized according to the buses they require. In other words, whether they would require an on-chip system bus, an external bus of the chip, or both. By way of example, such a characterization was done in FIG. 11 above, at the conceptual level. The characterization can be done by special coding of the request signals, as described above. [0154] According to a next step 1330, one of the inputted requests is identified that would use only available ones of the buses. If this step is repeated, a second (and a third) request could be identified concurrently by this step 1330. [0155] According to an optional next step 1340, the previous step 1330 can be performed by considering also rankings of the requests. The rankings (such as those of FIG. 12) can be preset, and given in the form of absolute rankings or relative rankings. The rankings may also consider the waiting history of a request, favoring one that has waited longer among equals. [0156] According to a next step 1350, it is inquired whether granting the above identified request would leave any of the buses available. If yes, execution reverts to step 1330, and another request is identified. [0157] If not, then according to a next step 1360, all requests identified so far are performed concurrently. This is accomplished by granting all the identified requests, preferably concurrently. Execution then may return to step 1310. [0158] Referring now to FIG. 14, a flowchart 1400 is used to illustrate a general method according to an embodiment of the invention. [0159] According to a step 1410, any additional requests are input, similarly to step 1310 above. [0160] According to a next step 1420, the inputted requests are characterized according to the buses they require, similarly to step 1320 above. [0161] According to a next step 1430, the requests are ranked, as discussed above. [0162] According to a next step 1440, the request with the highest priority is identified. [0163] According to a next step 1450, it is determined which buses would be idle if all the identified requests were granted. If none, then according to a next step 1460, the identified requests are granted, and execution may revert to step 1410. [0164] If not, then according to a next step 1470, the request with the next highest priority is identified. [0165] According to a next step 1480, it is inquired whether the last identified request is performable (if it were granted) only by would-be idle buses. If yes, then execution continues back to step 1450. [0166] If not, then according to a next step 1490 it is determined whether the last identified request was the last one of the inputted requests. If not, then execution continues with step 1470, to examine another request. If yes, then execution continues with step 1460. [0167] Referring now to FIG. 15, a flowchart 1500 is used to illustrate a particular method according to the invention. It will be appreciated that the steps of FIG. 15 show the operation of each functional block in the bus arbiter of FIG. 7 and FIG. 8. [0168] Step 1510: The request decoder 710 checks whether a bus request signal (REQ) has been input. If there is a bus request, a process flow goes to step 1520, while if there is no bus request, the request decoder 710 waits for a bus request in the step 1510. [0169] Step 1520: The request decoder 710 selects the functional block having the highest priority among one or those functional blocks submitting bus requests based on a pre-programmed priority algorithm, referring to the priority scheduler 720. The process flow goes to step 1530. [0170] Step 1530: A check is made as to whether the bus request signal of the functional block selected in the step 1520 is 2′b11 corresponding to set ES. If the bus request signal is 2′b11, the process flow goes to step 1540, while if not the process flow goes to step 1550. [0171] Step 1540: The request decoder 710 drives the system bus master selector 730 so that the functional block selected in the step 1520 may be granted system bus grant signal SGNT to use a system bus. The process flow goes to step 1620. [0172] Step 1550: It is checked that the bus request signal of the functional block selected in the step 1520 is 2′b01 corresponding to set SO. If the bus request signal is 2′b01, the process flow goes to step 1560, while if not, the process flow goes to step 1590. [0173] Step 1560: A check is made as to whether there are functional blocks submitting bus request signals 2′b10 corresponding to set EO among the remaining functional blocks except the functional block selected in the step 1520. If those functional blocks exist, the process flow goes to the step 1570, while if they do not exist, the process flow goes to the step 1580. [0174] Step 1570: The request decoder 710 selects the functional block having the highest priority among the functional blocks in set EO. Then, the request decoder 710 drives the system bus master selector 730 so that a system bus grant signal SGNT is given to the functional block selected in the step 1520, while the request decoder 710 drives the external bus master selector 750 so that an external bus grant signal EGNT is given to the functional block selected in the step 1570. The process flow goes to step 1620. [0175] Step 1580: The request decoder 710 drives only the system bus master selector 730 so that the system bus grant signal SGNT is given to the functional block selected in the step 1520. The process flow goes to the step 1620. [0176] Step 1590: A check is made as to whether there are functional submitting bus request signals 2′b01 corresponding to set SO among the remaining functional blocks except the functional block selected in the step 1520. If those functional blocks exist, the process flow goes to step 1600, while if they do not exist, the process flow goes to step 1610. [0177] Step 1600: The request decoder 710 selects the functional block having the highest priority among the functional blocks in set SO. Then, the request decoder 710 drives the external bus master selector 750 so that an external bus grant signal EGNT is given to the functional block selected in the step 1520, while it drives the system bus master selector 730 so that the system bus grant signal SGNT is given to the functional block selected in the step 1520. The process flow goes to the step 1620. [0178] Step 1610: The request decoder 710 drives only the external bus master selector 750 so that the external bus grant signal EGNT is given to the functional block selected in the step 1520. The process flow goes to the step 1620. [0179] Step 1620: If the system bus master selector 730 selects one system bus master, the system bus master selector 730 drives the system bus slave selector 740 so that an appropriate system bus slave may be selected depending on the operation of the selected system master. In particular, if the selected system bus master is the element of set ES, the system bus slave selector 740 drives the external memory controller 440, which is a system bus slave, so that the functional block selected in the step 1520 simultaneously uses the system bus and the external bus. If the external bus master selector 750 selects one external bus master, the external bus master selector 32 drives the external memory controller 440 to control the external bus. The priority scheduler 720 readjusts the priority of each functional block according to a program. The process flow then goes to step 1630. [0180] It should be clarified that step 1620 is optional. In another embodiment of the invention, step 1620 is not included, and the process flow goes directly to step 1630. [0181] Step 1630: A check is made as to whether the operation of the selected functional blocks has been completed. If the operation is complete, the process flow returns to the step 1510, while if not, the process flow continues to wait for the completion in the step 1630. [0182] Referring now to FIG. 16, snapshots are shown resulting from bus arbitration according to a bus arbitration scheme according to an embodiment of the present invention. It will be appreciated that relevant signals are shown next to requests, for characterizing the requests in terms of which buses they would use. [0183] One of the important aspects of the invention is that requests are treated non-hierarchically for use by masters of the chip's system bus and external bus, whether the latter are on the chip or off the chip. That is, blocks of set A are addressed, not just S. Another aspect to note is that in some instances, disparate requests are performed simultaneously. Moreover, the priority of all functional blocks, on chip and off-chip can be programmed using a single arbiter 495. [0184]FIG. 17 illustrates a Table 3 for comparing performance of a scheme of the invention compared to those in the prior art. Table 3 works in terms of probabilities. [0185] For Table 3, the following assumptions have been made. First, that the rate at which each functional block performs its operation is made equal if the functional blocks having the same priority performs their operations for a sufficient period of time. Second, that the sets of functional blocks, i.e., sets EO, ES, and SO, all have one or more elements. In Table 3, the probability of performing an operation is determined per set. [0186] For Table 3, bus utilization is defined as the utilization rate of each bus during actual operation of each functional block having bus ownership. The case in which the functional block having system bus ownership cannot perform its operation due to the absence of external bus ownership (as shown in FIG. 3D) is excluded from the bus utilization of the conventional hierarchical bus arbitration scheme in Table 3. [0187] As is evident from Table 3, according to the exclusive bus arbitration scheme, the probability of performing operation by all elements is the same. However, according to the conventional hierarchical bus arbitration scheme and the present invention, each set has a different value in the probability thereof. In the conventional exclusive bus arbitration scheme, the probability that the elements of sets EO, ES, and SO having bus ownership will perform their operations may be obtained from Equations (1), (2), and (3): n  ( EO ) n  ( A ) � 1 n  ( EO ) = 1 n  ( A ) ( 1 ) n  ( ES ) n  ( A ) � 1 n  ( ES ) = 1 n  ( A ) ( 2 ) n  ( SO ) n  ( A ) � 1 n  ( SO ) = 1 n  ( A ) ( 3 ) [0188] Furthermore, the bus utilization when performing an operation by the elements of set EO, ES and SO according to the conventional exclusive bus arbitration scheme may be obtained from Equation (4): ( 1 n  ( A ) � n  ( EO ) � 1 2 ) + ( 1 n  ( A ) � n  ( ES ) � 1 ) + ( 1 n  ( A ) � n  ( SO ) � 1 2 ) = n  ( EO ) + 2  n  ( ES ) + n  ( SO ) 2  n  ( A ) ( 4 ) [0189] In the conventional hierarchical bus arbitration scheme, the probability that the elements of sets EO, ES, and SO having bus ownership will perform their operations may be obtained from Equations (5), (6), and (7): ( n  ( SO ) n  ( S ) � 1 n  ( EO ) ) + ( n  ( ES ) n  ( S ) � 1 n  ( EO ) � 1 2 ) = n  ( ES ) + 2  n  ( SO ) 2  n  ( S )  n  ( EO ) ( 5 ) n  ( ES ) n  ( S ) � 1 n  ( ES ) � 1 2 = 1 2  n  ( S ) ( 6 ) n  ( SO ) n  ( S ) � 1 n  ( SO ) = 1 n  ( S ) ( 7 ) [0190] Furthermore, the bus utilization according to the conventional hierarchical bus arbitration scheme may be obtained from Equation (8): ( n  ( ES ) + 2  n  ( SO ) 2  n  ( S )  n  ( EO ) � n  ( EO ) � 1 2 ) + ( 1 2  n  ( S ) � n  ( ES ) � 1 ) + ( 1 n  ( S ) � n  ( SO ) � 1 2 ) = 4  n  ( SO ) + 3  n  ( ES ) 4  n  ( S ) ( 8 ) [0191] In the present invention, the probability that the elements of sets EO, ES, and SO having bus ownership will perform their operations may be obtained from Equations (9), (10), and (11): ( n  ( EO ) n  ( A ) � 1 n  ( EO ) ) + ( n  ( SO ) n  ( A ) � 1 n  ( EO ) ) = n  ( EO ) + n  ( SO ) n  ( A )  n  ( EO ) ( 9 ) n  ( ES ) n  ( A ) � 1 n  ( ES ) = 1 n  ( A ) ( 10 ) ( n  ( SO ) n  ( A ) � 1 n  ( SO ) ) + ( n  ( EO ) n  ( A ) � 1 n  ( SO ) ) = n  ( SO ) + n  ( EO ) n  ( A )  n  ( SO ) ( 11 ) [0192] Furthermore, the bus utilization according to the present invention may be obtained from Equation (12): ( n  ( E ) + n  ( SO ) n  ( A )  n  ( EO ) � n  ( EO ) � 1 2 ) + ( 1 n  ( A ) � n  ( ES ) � 1 ) + ( n  ( SO ) + n  ( EO ) n  ( A )  n  ( SO ) � n  ( SO ) � 1 2 ) = 1 ( 12 ) [0193] As described above, the conventional hierarchical arbitration scheme and the bus arbitration scheme according to the present invention offer high probability that each functional block having bus ownership can perform its operation compared to the conventional exclusive bus arbitration scheme. [0194] Furthermore, the bus arbitration scheme according to the present invention, the conventional hierarchical bus arbitration scheme, and the conventional exclusive bus arbitration scheme are in order of the size for a bus utilization (Equation(12)>Equation(8)>Equation(4) ). Accordingly, the bus arbitration scheme according to the present invention allows for the programming of the priority of all functional blocks and a resulting high bus utilization. [0195] A person skilled in the art will be able to practice the present invention in view of the description present in this document, which is to be taken as a whole. Numerous details have been set forth in order to provide a more thorough understanding of the invention. In other instances, well-known features have not been described in detail in order not to obscure unnecessarily the invention. [0196] While the invention has been disclosed in its preferred form, the specific embodiments thereof as disclosed and illustrated herein are not to be considered in a limiting sense. Indeed, it should be readily apparent to those skilled in the art in view of the present description that the invention can be modified in numerous ways. The inventor regards the subject matter of the invention to include all combinations and subcombinations of the various elements, features, functions and/or properties disclosed herein. [0197] The following claims define certain combinations and subcombinations, which are regarded as novel and non-obvious. Additional claims for other combinations and subcombinations of features, functions, elements and/or properties may be presented in this or a related document. Referenced byCiting PatentFiling datePublication dateApplicantTitleUS6954387Jul 15, 2003Oct 11, 2005International Business Machines CorporationDynamic random access memory with smart refresh schedulerUS7020807 *Sep 19, 2001Mar 28, 2006Koninklijke Philips Electronics N.V.Data communication bus traffic generator arrangementUS7091743Oct 7, 2003Aug 15, 2006International Business Machines CorporationData acknowledgment using impedance mismatchingUS7127540 *May 29, 2003Oct 24, 2006Samsung Electronics Co., Ltd.Apparatus and method for controlling frequency of bus useUS7185133 *Jun 2, 2005Feb 27, 2007Renesas Technology Corp.Data processorUS8490107Aug 8, 2011Jul 16, 2013Arm LimitedProcessing resource allocation within an integrated circuit supporting transaction requests of different priority levelsUS8842513Sep 15, 2010Sep 23, 2014Samsung Electronics Co., Ltd.Method of data modulation and demodulation in SoCUS20090248972 *Jun 11, 2009Oct 1, 2009Ware Frederick ADynamic Memory Supporting Simultaneous Refresh and Data-Access Transactions* Cited by examinerClassifications U.S. Classification710/240International ClassificationG06F13/36, G06F13/362, G06F13/364Cooperative ClassificationG06F13/364European ClassificationG06F13/364Legal EventsDateCodeEventDescriptionMar 14, 2013FPAYFee paymentYear of fee payment: 8May 26, 2009FPAYFee paymentYear of fee payment: 4Jan 9, 2007CCCertificate of correctionJan 31, 2001ASAssignmentOwner name: SAMSUNG ELECTRONICS CO., LTD., KOREA, REPUBLIC OFFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:KIM, YOUNGSIK;LEE, YUN-TAE;REEL/FRAME:011513/0949Effective date: 20010131RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services