Abstract:
A direct memory access controller controls many direct memory access ports using a token passing scheme. The system multiplexes the port&#39;s accesses to external random access memory by daisy-chaining a loop of direct access memory ports and passing the token around to each port. Once a port receives the token it may request as many random access memory accesses as it requires. These accesses may be either read operations or write operations with both using the same multiplexed data bus. The latency inherent in reading an external RAM causes no loss in the access efficiency. When the port has completed its data transfer or if the port does not require a data transfer, the token is passed to the next direct memory access port for its data transfer. The token is passed around to all connected ports until all have had an opportunity to complete any memory transfers which they required. Each port is identical except for a binary identification code that is used to represent each port. The system can accommodate as many ports as necessary and additional ports can be added at a subsequent time.

Description:
This is a File Wrapper Continuation of copending application Ser. No. 07/913,845 filed on Jul. 15, 1992, abandoned. 
    
    
     FIELD OF THE INVENTION 
     This invention relates to the field of direct memory access systems particularly those systems which multiplex access to external random access memories using a token passing scheme. 
     BACKGROUND OF THE INVENTION 
     Direct memory access (DMA) is a technique that is used to allow various I/O devices to store data in and read data from a random access memory (RAM) while the CPU is performing other tasks. Direct memory access allows the I/O devices to bypass the CPU and interact with the RAM directly. A direct memory access system can be structured so that it has its own channel directly to the memory or alternatively the DMA system can share the same channel with the CPU, taking advantage of the address bus, the data bus, and the control bus used by the CPU. If the DMA system is using the channel to access the data memory, the CPU is free to perform its own programmed tasks as long as it does not need to access the data memory or use the busses. 
     There are many operations that a CPU must perform which do not require access to the memory, but instead require it to perform a process on a word, or words, already within its internal registers, such as an ADD operation or a SHIFT operation. During the time that the CPU is busy performing these other operations the DMA system can perform a transfer of data between the RAM and an I/O device. This DMA transfer can occur in the form of either a read operation or a write operation. 
     Another way that the DMA system can gain access to the memory is by using a method called cycle stealing. Using this method if an I/O device connected to the DMA system wishes to access memory it initiates a DMA request signal. When the CPU receives this signal it completes its current instruction and suspends operation or idles for the next clock cycle. When the DMA transfer is complete the CPU then resumes its normal programmed operation. This method is not as efficient as the first because the CPU does not perform additional tasks while a cycle stealing DMA transfer takes place but rather sits and waits until the transfer is complete. 
     Many I/O devices can be connected to one DMA controller as components of the DMA system. Each device may require access to RAM at different times or at the same time. When more than one device requests access to RAM at the same time, the system must employ some method to choose which device will be given access to the memory first. One such method is to assign priorities to the devices connected to the DMA controller, so that the device with the highest priority will be given access to the RAM first. If there is time left after a higher priority device accesses the RAM, then a lower priority device will be given access to the RAM after the higher priority device has completed its transfer. 
     The DMA transfer can continue for a programmed period of time, until the transfer is complete, or until the CPU requires access to the memory. Once the transfer is ended for any of the above reasons, control of the memory access channel reverts back to the CPU until it no longer requires access and the DMA system has requested a transfer, or in some cases until the DMA controller is able to steal a cycle to perform another transfer. 
     What is needed is a direct memory access transfer system which allows access to external memory by multiple ports, each port in turn. The system&#39;s architecture should easily accommodate future expansion. Further, a direct memory access transfer system is needed which will allow each port to perform as many data transfers as it requires before the next port is allowed access to the external memory. 
     SUMMARY OF THE INVENTION 
     A direct memory access controller controls many direct memory access ports using a token passing scheme. The system multiplexes the port&#39;s accesses to external random access memory by daisy-chaining a loop of direct access memory ports and passing the token around to each port. Once a port receives the token it may request as many random access memory accesses as it requires. These accesses may be either read operations or write operations with both using the same multiplexed data bus. The latency inherent in reading an external RAM causes no loss in the access efficiency. When the port has completed its data transfer or if the port does not require a data transfer, the token is passed to the next direct memory access port for its data transfer. The token is passed around to all connected ports until all have had an opportunity to complete any memory transfers which they required. Each port is identical except for a binary identification code that is used to represent each port. The system can accommodate as many ports as necessary and additional ports can be added at a subsequent time. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a typical direct memory access data transfer system according to the present invention having one controller and three connected direct memory access ports. 
     FIG. 2 is a timing diagram for a direct memory access port receiving a token and then passing it without performing any RAM accesses according to the present invention. 
     FIG. 3 is a timing diagram for a direct memory access port receiving a token, requesting two RAM accesses, then passing the token according to the present invention. 
     FIG. 4 is a timing diagram for a direct memory access port receiving a token, requesting two RAM accesses, the second of which is the last in the direct memory access according to the present invention. 
     FIG. 5 is a timing diagram for a direct memory access port receiving a token, requesting two writes to RAM, then passing the token according to the present invention. 
     FIG. 6 is a timing diagram for a direct memory access port receiving a token, requesting two reads from RAM, passing the token, then receiving the requested bytes according to the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The direct memory access controller for an integrated circuit of the preferred embodiment is made up of one direct memory access controller (DMACON) and many direct memory access ports (DMAPORTs) as shown in FIG. 1. The DMAPORTS 2 and the DMACON 1 are daisy-chained together by the token signal line 9 and also connected by a request line 3, (REQ), an acknowledge line 4, (ACK), a direct memory access done line 6, (DONE), an identification number bus 8, (ID), a bi-directional data bus 7, (DATA), and a direction of current transfer line 5 (DIR). 
     Each DMAPORT 2 is identical with the exception of an identification number that is used to represent each port individually. This identification number is a binary representation of the particular port&#39;s identification number which is programmed by connections to either power or ground and is carried by the identification number bus 8 to the DMACON 1 during data transfers. The size of the identification number bus 8 will vary depending on the number of ports that are connected to the DMACON 1, but must be big enough to carry the binary representation of each port&#39;s identification number. For example, the system shown in FIG. 1 has three DMAPORTs 2. Therefore to fully represent each port&#39;s identification number, the ID bus 8 must be at least two bits wide, but if two more DMAPORTs 2 were added to the system the ID bus 8 would have to be expanded to at least three bits. The width of the bi-directional data bus 7 can also vary depending on what size is most convenient, works most efficiently and what size the data blocks are that are to be transferred. The system shown in FIG. 1 has an eight bit wide bi-directional data bus. 
     Each module on the integrated circuit requiring access to an external random access memory interfaces with the DMA system through a DMAPORT 2. The DMAPORT 2 then handles the mechanics of the particular read or write operation with the RAM and transfers the data through the DMACON 1. 
     The DMACON 1 controls the frequency of RAM accesses by the DMAPORTS 2 with one clock cycle pulses on the acknowledge signal line 4 (ACK). The clock cycle following ACK 4 rising from a low potential to a high potential is reserved for a read operation and the clock cycle following ACK 4 falling from a high potential to a low potential is reserved for a write operation. The DMACON 1 also maintains and updates the RAM addresses and byte transfer counts for each of the DMAPORTs 2. 
     The DMAPORTs 2 time-multiplex access to the DMACON 1, and therefore the RAM itself by using a token passing scheme. A token is passed around the loop such that the DMAPORT 2 with the token is allowed sole access to the DMACON 1 and the external memory. The DMAPORT 2 can keep the token for as long as it requires to complete its data transfer. When the DMAPORT 2 completes its required RAM access, it passes the token to the next DMAPORT 2 in the daisy-chained loop. The signal lines REQ 3 and ACK 4 are used to control the timing of this scheme and to determine the location of the token at any one time. 
     During reset of the system, the token is generated by the DMACON 1 and passed along the daisy chain to the first DMAPORT 2. When a DMAPORT 2 receives the token, it has the choice of either requesting access to the memory or passing the token to the next DMAPORT 2 on the daisy chain. If the DMAPORT 2 does not currently require access to the RAM it passes the token on to the next DMAPORT. 
     The timing diagram for a DMAPORT 2 receiving the token and then passing it is illustrated in FIG. 2. The DMAPORT 2 receives the token and if it does not require access to RAM, it drives REQ 3 low during the first clock cycle after receiving the token. During the second cycle after receiving the token, the current DMAPORT 2 releases the drive on REQ 3, allowing REQ to float, and driving the token out to the next DMAPORT 2. 
     The timing diagram for a DMAPORT 2 receiving the token and then requesting access to external RAM is illustrated by FIG. 3. If the DMAPORT 2 does require RAM access when it receives the token it asserts REQ 3 during the next clock cycle after receiving the token and holds it high until that DMAPORT 2 has completed its accesses and the token is passed to the next DMAPORT 2. Every ACK 4 pulse while REQ 3 is asserted is interpreted by the DMAPORTs 2 and the DMACON 1 as a RAM access cycle for the port with the token. The DMAPORT 2 may keep the token for as many RAM cycles as it desires. To release the token the DMAPORT 2 drives REQ 3 low during the first clock cycle after any ACK 4 pulse. During the clock cycle following REQ 3 being driven low, the driver on REQ 3 should be disabled allowing the request line REQ 3 to float and the token is driven to the next DMAPORT 2. FIG. 3 shows the timing for a DMAPORT 2 receiving the token, getting two RAM accesses, and releasing the token to the next DMAPORT 2. 
     There is one situation where the DMACON 1 will force a DMAPORT 2 to pass the token before its required transfer is complete. The DMACON 1 keeps a transfer byte count which is decremented each time a byte of data is transferred. When the transfer byte count reaches zero the direct memory access for the channel is over and the token must be passed to the next DMAPORT. The DMACON 1 indicates the end of a direct memory access by driving DONE 6 to a high potential for a single clock cycle after an ACK 4 pulse. During the clock cycle after the DONE 6 pulse, the DMAPORT 2 must drive REQ 3 low. The token is passed and the driver on REQ 3 is released during the following clock cycle allowing REQ 3 to float. A DMAPORT 2 receiving two RAM cycles, the second of which is the final byte in the direct memory access, is shown in FIG. 4. 
     With the DMAPORTs 2 following all the rules already outlined for the timing for REQ 3, the DMACON 1 can keep track of all token passes so that it knows which DMAPORT 2 is currently accessing the external RAM. The DMACON 1 uses a sequencer which is reset during the power-on sequence for the IC and is incremented every time that the token is passed to another DMAPORT 2. 
     Each DMAPORT 2 is allowed to define its own rules for how long it will keep the token before it passes the token to the next DMAPORT 2. The rules that a DMAPORT 2 can choose from are to keep the token for only one RAM access, to perform as many RAM accesses as possible while holding the token only a preprogrammed number of clock cycles, or to fill or empty local memory storage that is connected to the DMAPORT 2. This local memory storage is a first-in first-out stack that is connected to the DMAPORT 2 and can be filled or emptied according to the direction of the transfer that the DMAPORT 2 requests. 
     FIG. 5 illustrates the timing diagram for a DMAPORT 2 writing two bytes of data to external RAM. When the token is passed to the DMAPORT 2, REQ 3 is driven to a high potential by the DMAPORT 2, because the DMAPORT 2 does require a memory access. Because this memory access is a write operation DIR 5 is dropped to a low potential at the same time that REQ 3 is driven high. The DMAPORT 2 continues to hold DIR 5 at a low potential until the clock cycle when the token is passed. Simultaneous to the release of the REQ driver by the DMAPORT 2, the DIR driver is disabled allowing both REQ 3 and DIR 5 to float. The data bytes to be written to the RAM are driven on to the data bus 7 one at a time following each of the ACK 4 pulses. The only time that a DMAPORT 2 is allowed to drive the data bus 7 is during the clock cycle following ACK 4 dropping from a high potential to a low potential. 
     There is a latency inherent to any integrated circuit reading an external RAM because of the nature of the memory. This latency complicates a DMAPORT&#39;s reading of data from the external memory. The present direct memory access system has at most a three stage pipe line delay in the read operation. The DMACON 1 adds two pipe line delays to allow time for the calculation of the external RAM addresses where the data is to be read from. The sequencer that performs the RAM access adds the third stage of pipe line delay while waiting for the requested byte of data to return from the external RAM. 
     The latency in a read operation is seen by the DMAPORT 2 as the delay between the clock cycle during which both REQ 3 and ACK 4 are high, and the arrival of a byte of data from the external memory. To account for the fact that the DMAPORT 2 requesting the read operation may have already passed the token before the data arrives from the external memory, a DMAPORT 2 must be able to retrieve data from the data bus 7 irrespective of the position of the token. Because the DMAPORT 2 requesting the read operation may not still have the token when the data is transmitted from the external memory, the DMAPORT&#39;s 2 identification number is put on the ID bus 8 and sent along with the data byte on the data bus 7. When a DMAPORT 2 sees its identification number on ID 8, it latches the data from the data bus 7. 
     The timing diagram for a read operation by a DMAPORT 2 is illustrated in FIG. 6. When the token is passed to the DMAPORT 2 it drives REQ 3 to a high potential because it does need to execute data transfers. Because the RAM accesses which the DMAPORT 2 requires are read operations, DIR 5 is driven to a high potential by the current DMAPORT 2. Two ACK 4 pulses are generated while the DMAPORT 2 performs the two read operations. Due to the latency of reading from any external device the data can not be sent when it is requested and the DMAPORT 2 may have passed the token to the next DMAPORT 2 before it receives the data it requested. To insure that the data will go to the DMAPORT 2 that requested it, that DMAPORT&#39;s identification number is sent on the ID bus 8 at the same time the data is sent on the data bus 7. Read operations only occur during the clock cycle following ACK 4 rising from a low potential to a high potential so the requested data bytes are driven on to the data bus 7 during the next two ACK 4 pulses and the identification number of the requesting DMAPORT 2 is driven onto the ID bus 8 at the same time. The requesting DMAPORT 2 will latch the data from the data bus 7 when it sees its identification number on the ID bus 8. 
     The time-multiplexing scheme used, based on the timing of ACK 4 allows both read and write data bytes to be carried by the data bus 7. Data that is read from the external memory and transmitted to a DMAPORT 2 is only allowed on the data bus 7 during the clock cycle following ACK 4 rising from a low potential to a high potential. Data that is transmitted from a DMAPORT 2 that is to be written to the external memory is only allowed on the data bus 7 during the clock cycle following ACK 4 falling from a high potential to a low potential. 
     The architecture of this direct memory access data transfer system is very extensible. All that is required to add additional DMAPORTs 2 is to add additional states to the DMACON&#39;s 1 sequencer and to add enough lines to the ID bus 8 so that it can fully represent the binary identification number of each DMAPORT 2. 
     The present invention is described above relative to the preferred embodiment. Modifications that occur to one of ordinary skill in the art after reading this disclosure are deemed within the spirit and scope of the invention.