Embedded system with instruction prefetching device, and method for fetching instructions in embedded systems

In a method for fetching instructions in an embedded system, a predicted one of a set of the instructions stored in a memory device is fetched and is subsequently stored in an instruction buffer when a system bus is in a data access phase. When a processor generates an access request for the memory device, the predicted one of the instructions stored in the instruction buffer is provided to the system bus for receipt by the processor upon determining that the predicted one of the instructions stored in the instruction buffer hits the access request from the processor. An embedded system with an instruction prefetching device is also disclosed.

BACKGROUND

The invention relates to an embedded system, more particularly to an embedded system with an instruction prefetching device and to a method for fetching instructions in embedded systems.

FIG. 1illustrates a conventional embedded system5that comprises a system bus54, a processor51coupled to the system bus54, a memory controller52coupled to the system bus54, a peripheral controller53coupled to the system bus54, and a memory device55coupled to the memory controller52. The peripheral controller53may be various controllers or drivers coupled to the system bus54and can be controlled by the processor51. For example, in a cellular phone applications, the peripheral controller53may be a controller to control the LCD or a controller to control the keypad of a cellular phone. Rather than being coupled to the system bus54directly, in this example the memory device55is coupled to the memory controller52for being controlled and being accessed by the memory controller52.

When the processor51wants to fetch instruction from the memory device55, the processor51will issue an access request having a target address directed to the memory controller52. The memory controller52then fetches an instruction from the memory device55according to the access request received from the processor51, and provides the instruction to the system bus54for receipt by the processor51. When the processor51is accessing the memory device55, the system bus54will be occupied since it has to relay the access requests issued by the processor51to the memory controller52and relay the fetched instructions from the memory controller52to the processor51.

Aside from accessing the memory device55, the processor51can also access the peripheral controller53. When the processor51wants to access the peripheral controller53, the processor51will issue an access request having a target address directed to the peripheral controller53. Apparently, when the processor51is accessing the peripheral controller53, the system bus54will be occupied since it has to relay the access requests and information corresponding to the access requests between the processor51and the peripheral controller53.

Besides, the peripheral controller53and another peripheral controller (not shown) can also exchange information through the system bus54, causing the system bus54to be occupied by the two peripheral controllers.

Although the conventional embedded system has a lower system performance, it works well in various applications. However, as the embedded system5becomes more complex, the embedded system5is required to run at higher speeds to achieve better performance. More particularly, access latency occurs during fetching of an instruction from the memory device55after the processor51sent out an access request (i.e., fetching cycle), so the performance of the processor51is degraded. For the conventional embedded system, the fetching cycle occupies approximately 30%˜50% of the instruction cycle of the processor51, so access latency is a problem which cannot be ignored.

Two methods are proposed in the related art in order to overcome the above problem.

1. An additional cache memory (L2 cache) is incorporated to increase the memory bandwidth, so as to enhance the performance of the embedded system. However, the cache memory (such as an SRAM) has a higher cost and a relatively small memory capacity.

2. When the processor51executes an instruction, fetching of a next instruction is executed at the same time. This kind of solution is referred to as instruction prefetching. However, the occupation period of the system bus54becomes longer when the next instruction is among a series of consecutive instructions or has too many branch instructions. Data access to or from the peripheral controller53must wait until fetching of the next instruction has been completed by the processor51. Similarly, when two peripheral controllers53are exchanging information, the processor51also have to wait a period for the system bus54to be freed.

In other words, as long as the system bus54is occupied, other information access processes relying on the system bus54have to wait until the system bus54is freed.FIG. 2is a timing chart to illustrate an operating example of the conventional embedded system5. The system bus54is occupied by the instruction fetch phase and the data access phase in turns. In the instruction fetch phase, the processor51communicates with the memory controller52and instructions or data stored in the memory device55are fetched; whereas in the data access phase, the processor51communicates with the peripheral controller53and requests the peripheral controller53to perform certain actions. Alternately, in the data access phase, the peripheral controller53is communicating with another peripheral controller (not shown) through the system bus54. As such, when the system bus54is in the data access phase while one peripheral controller53is communicating with another peripheral controller53, the processor51have to remain idle for a period of time (about two bus cycles) before it is allowed to communicate with the memory controller52.

In addition, when the system bus54is occupied since the processor51is accessing the peripheral controller53or two peripheral controllers53are exchanging information, even if the memory controller52is idle the processor51still have to wait for a period of time (about two bus cycles) before it is allowed to communicate with the memory controller52. Therefore, it is preferred that the memory controller52prefetches instructions from the memory device55while the system bus54is occupied by the processor51and the peripheral controller53or by two peripheral controllers. After the system bus54is freed, the memory controller52can send the prefetched instructions, which conform to the requirements of the processor51, to the processor51in response to the request issued by the processor51. The performance of the whole embedded system is therefore increased. An objective of the present invention is to propose a solution to this kind of problem.

SUMMARY

Therefore, the object of the present invention is to provide an instruction prefetching device and a method for prefetching instructions. The disclosed device and method allow a memory controller to prefetch instructions from a memory device. Even if the memory device is not a cache memory, the efficiency of fetching instructions is still increased greatly.

According to one aspect of the present invention, there is provided a method for fetching instructions in an embedded system that includes a system bus, a processor coupled to the system bus, a peripheral controller coupled to the system bus, and a memory device having a set of the instructions stored therein. The method comprises the steps of:

a) determining whether the system bus is in the data access phase;

b) fetching a predicted one of the instructions from the memory device, and storing the predicted one of the instructions in an instruction buffer when the system bus is in the data access phase;

c) determining whether the processor generates an access request for the memory device;

d) determining whether the predicted one of the instructions stored in the instruction buffer hits the access request from the processor upon determining that the processor generated the access request; and

e) providing the predicted one of the instructions stored in the instruction buffer to the system bus for receipt by the processor when the predicted one of the instructions stored in the instruction buffer hits the access request from the processor.

According to another aspect of the present invention, an embedded system comprises:

a system bus for signaling and data transactions;

a processor coupled to the system bus;

a peripheral controller coupled to the system bus;

a memory device having a set of instructions stored therein; and

an instruction prefetching device coupled to the system bus and the memory device, the instruction prefetching device monitoring signal transaction on the system bus and fetching a predicted one of the instructions from the memory device when the system bus is in the data access phase, the instruction prefetching device receiving an access request for the memory device from the processor through the system bus, and providing the predicted one of the instructions to the system bus for receipt by the processor when the predicted one of the instructions hits the access request from the processor.

According to still another aspect of the present invention, an instruction prefetching device is adapted for use in an embedded system that includes a system bus, a processor coupled to the system bus, a peripheral controller coupled to the system bus, and a memory device having a set of instructions stored therein. The instruction prefetching device comprises:

a prefetching controller coupled to the system bus and adapted to monitor transaction on the system bus;

a memory controller coupled to the prefetching controller and the memory device; and

an instruction buffer coupled to the prefetching controller and the memory controller;

the prefetching controller enabling the memory controller to fetch a predicted one of the instructions from the memory device and to store the predicted one of the instructions in the instruction buffer when the prefetching controller determines that the system bus is in the data access phase;

the prefetching controller being adapted to receive an access request for the memory device from the processor through the system bus when the system bus is not in the data access phase, and being adapted to provide the predicted one of the instructions stored in the instruction buffer to the processor through the system bus when the predicted one of the instructions stored in the instruction buffer hits the access request from the processor.

DETAILED DESCRIPTION

Referring toFIG. 3, the preferred embodiment of an embedded system1according to the present invention is shown to include a system bus11, a processor13, a peripheral controller14, a memory device12, and an instruction prefetching device3.

The system bus11is used for signaling and data transactions. As known to those skilled in the art, the system bus11may include an address bus, a control bus, and a data bus, etc.

The processor13is coupled to the system bus11for controlling communication and data transmission within the embedded system1or with other external devices (not shown). The processor13may further comprise a cache memory (not shown).

The peripheral controller14is coupled to the system bus11. In a cellular phone or other handheld systems, the peripheral controller14may be a controller to control a peripheral device, such as an LCD display, a keypad, an IR (intra-red) device, or a USB (Universal Serial Bus) device.

The memory device12has a set of instructions or data stored therein. In this embodiment, the memory device12may be an internal memory located inside the embedded system, or an external memory located outside the embedded system. The memory device12may be a ROM, FLASH, SRAM, DRAM or similar electronic devices for storing instructions of the processor13.

The instruction prefetching device3is coupled to the system bus11and the memory device12and serves as an interface for transmission and control between the processor13and the memory device12. The instruction prefetching device3monitors signal transaction on the system bus11and controls a memory controller31to fetch or to prefetch instruction from the memory device12. More specifically, when the system bus11is in the data access phase, the instruction prefetching device3prefetches a predicted one of the instructions from the memory device12. The instruction prefetching device3receives an access request for the memory device12from the processor13through the system bus11, and provides the predicted one of the instructions to the system bus11for receipt by the processor13when the predicted one of the instructions hits the access request from the processor13.

In this embodiment, the instruction prefetching device3includes a prefetching controller33coupled to the system bus11for monitoring signal transaction on the system bus11, a memory controller31coupled to the memory device12and the prefetching controller33, and an instruction buffer32coupled to the prefetching controller33and the memory controller31. The prefetching controller33enables the memory controller31to fetch or prefetch instructions from the memory device12. More specifically, the prefetching controller33enables the memory controller31to either fetch instruction, which is currently requested by the processor13, from the memory device12, or prefetch instruction, which is predicted to be requested by the processor13, from the memory device12. The instructions fetched (or prefetched) by the memory controller31are stored in the instruction buffer32. If the processor13is performing a loop function and repeating executing a single instruction, the prefetching controller33can send the instruction stored in the instruction buffer32to the processor13directly without fetching the instruction from the memory device12repeatedly.

The system bus11is in the data access phase when the processor13is accessing the peripheral controller14through the system bus11, or when the peripheral controller14is communicating with another peripheral controller (not shown) through the system bus11. When the prefetching controller33determines that the system bus11is in the data access phase, the prefetching controller33enables the memory controller31to prefetch a predicted one of the instructions from the memory device12and to store the predicted one of the instructions in the instruction buffer32. The prefetching controller33receives an access request from the processor13through the system bus11when the system bus11is in the instruction fetching phase, and provides a predicted one of the instructions stored in the instruction buffer32to the processor13through the system bus11when the predicted one of the instructions stored in the instruction buffer32hits the access request from the processor13. It is noted that the predicted one of the instructions is determined by the prefetching controller33according to a previous instruction from the memory device12that was accessed by the processor13.

The prefetching controller33determines whether instruction prefetching is allowed or not through monitoring the target address of signal transmitted through the system bus11. When the prefetching controller33finds that the target address of signal transmitted through the system bus11points to the peripheral controller14or another peripheral controller, the prefetching controller33can determine that the system bus11is occupied and the memory controller31is in an idle status. In other words, the prefetching controller33determines that the system bus11is in the data access phase when the prefetching controller33finds that the target address of signal transmitted through the system bus11points to the peripheral controller14or another peripheral controller. The prefetching controller33can then enable the memory controller31to prefetch instructions from the memory device12. If, on the other hand, the prefetching controller33finds that the target address of signal transmitted through the system bus11points to the prefetching controller33itself, the prefetching controller33can determine that the system bus11is occupied due to instruction fetching and the memory controller31is responsible for providing currently requested instructions to the processor13. Therefore the prefetching controller33may not be allowed to enable the memory controller31to prefetch instructions from the memory device12.

In other words, the prefetching controller33is allowed to enable the memory controller31to prefetch instructions from the memory device12when the system bus11is in the data access phase and the memory controller31is in the idle status.

Referring toFIG. 4, there is shown a flow chart to illustrate how the instruction prefetching device3fetches instructions in the embedded system1of the preferred embodiment. In step51, when a transaction is started on the system bus11, the prefetching controller33determines whether the system bus11is in the data access phase. More specifically, the prefetching controller33examines the target address of the transaction on the system bus11so as to determine whether the system bus11is in the data access phase or not. If the target address of the transaction on the system bus11does not point to the prefetching controller33, the prefetching controller33determines that the system bus11is in the data access phase and step52will be performed next. If, on the other hand, the target address of the transaction on the system bus11points to the prefetching controller33itself, the prefetching controller33determines that the system bus11is not in the data access phase and step53will be performed next.

As mentioned, if the target address of the transaction on the system bus11does not point to the prefetching controller33, the prefetching controller33determines that the system bus11is in the data access phase and the memory controller is in the idle status. Therefore in step52the prefetching controller33enables the memory controller31to prefetch a predicted one of the instructions from the memory device12and to store the predicted one of the instructions into the instruction buffer32, and the flow proceeds back to step51. In view of sequential characteristics of the instructions executed by the processor13, the predicted one of the instructions is determined by the prefetching controller33according to previous instructions from the memory device12that were accessed by the processor13.

On the other hand, if the target address of the transaction on the system bus11points to the prefetching controller33itself, the prefetching controller33determines that the system bus11is not in the data access phase. Therefore in step53, the prefetching controller33determines whether the processor13generates an access request for the memory device12. When the processor13does not generate an access request for the memory device12, the flow proceeds back to step51. When the processor13does generate an access request for the memory device12, the flow proceeds to step54.

In step54, the prefetching controller33determines whether the predicted one of the instructions stored in the instruction buffer32hits the access request from the processor13when the prefetching controller33receives the access request from the processor13. If the predicted one of the instructions stored in the instruction buffer32hits the access request from the processor13, the flow proceeds to step55; otherwise, the flow proceeds to step56.

In step55, the prefetching controller33provides the predicted one of the instructions stored in the instruction buffer32to the system bus11for receipt by the processor13since the predicted one of the instructions stored in the instruction buffer32hits the access request from the processor13.

On the other hand, in step56, when the predicted one of the instructions stored in the instruction buffer32misses the access request from the processor13, the prefetching controller33enables the memory controller31to fetch an instruction corresponding to the access request from the processor13from the memory device12according to an address signal from the processor13. In addition, the prefetching controller33can further clear the instruction buffer32in step56so as to allow the instruction buffer32to store a next predicted one of the instructions stored in the memory device12. Besides, even though only one instruction buffer53is shown inFIG. 3, the instruction prefetching device3can include a plurality of instruction buffers so as to allow a plurality of prefetched instruction to be stored. An advantage of setting a plurality of instruction buffers is that the prefetching controller33can clear the instruction buffers less frequently. More specifically, only when all the instruction buffers are occupied by prefetched instructions and a new prefetched instruction is going to be stored into one of the instruction buffers, the prefetching controller33performs the clear operation on one or all of the instruction buffers.

The flow then proceeds to step55such that the prefetching controller33provides the proper instruction from the memory device12to the system bus11for receipt by the processor13.

Referring toFIG. 5, there is shown a timing chart of an operating example of the system bus11and a memory interface of the memory device12. In this example, when the system bus11is in the data access phase (DA1), the prefetching controller33enables the memory controller31to fetch a predicted instruction (IF2) stored in the memory device12and to store the predicted instruction (IF2) in the instruction buffer32such that the prefetching controller33can provide the predicted instruction (IF2) stored in the instruction buffer32to the system bus11for receipt by the processor13upon receiving an access request of the predicted instruction (IF2) from the processor13. Thus, only one bus cycle is needed for the processor13to fetch the predicted instruction (IF2) on the system bus11. Meanwhile, when the predicted instruction (IF2) is sent to the processor13through the system bus11, the prefetching controller33can perform prefetching of a next predicted instruction (IF3), simultaneously. Therefore, the efficiency of the system bus11can be improved, and the latency for fetching instructions by the processor13can be effectively shortened. For example, in the stage of data access (DA3), the embedded system1of the present invention has been advanced by about two bus cycles as compared to the timing chart ofFIG. 2for the aforesaid conventional embedded system.