Apparatus and method for address selection

An apparatus for address selection including a first storage element and a second storage element coupled to an input bus. The first storage element stores a first address segment and the second storage element stores a second address segment upon the receipt of respective complementary clock signals. An internal address bus propagates the address segments together.

TECHNICAL FIELD

Embodiments of the present invention relate to the field of memory devices and, in particular, to the addressing of memory devices.

BACKGROUND

Modern data communication and networking systems make extensive use of synchronous RAM for data processing.FIG. 1shows a memory architecture of a conventional networking application (e.g., a line card) using synchronous RAM to perform a variety of functions under the control of a processor. In the line card ofFIG. 1, data packets from a network are received by the processor and stored in a high-speed memory called a packet buffer. Subsequent processing of the data packets relies on data and instructions that are stored in the other memory structures shown inFIG. 1, such as a lookup table, a queue management memory, a statistics buffer and a policy buffer.

Each of these memories may use synchronous RAM of one type or another. Synchronous RAM is random access memory in which read and write operations are synchronized by the transitions of periodic signals called clock signals. In single data rate (SDR) synchronous RAM, data is transferred on each rising (or falling) edge of a clock signal. In order to achieve higher data transfer rates and maximize data throughput, double data rate (DDR) devices transfer data on both the rising and falling edges of the clock signal (or on the rising or falling edges of two separate clock signals). In order to avoid read/write data collisions on the data bus, separate buses can be provided for reading and writing data, and each bus can operate at double data rates to yield a quad data rate (QDR™) device. A further speed enhancement is achieved with burst-mode read and write operations. In burst-mode, the address provided to the memory specifies the starting point for a burst of data words, to or from the memory, which includes the addressed location and some number of contiguous locations.

The packet buffer is the most demanding memory requirement in the line card ofFIG. 1because data packets can be quite long and the buffer must be very deep to accommodate the network data rate. Packet buffers may use DDR, QDR™ or burst-mode QDR™ RAM. Depending on the specific application, the lookup table, the queue management memory, the statistics buffer and the policy buffer may use DDR, QDR™ or burst-mode QDR™ RAM to keep pace with the packet buffer.

Read and write operations in such memories may be characterized by a latency period. Read latency is the time period between the time that an address of a memory location is specified and the time that data is read from the memory location specified by the address. Write latency is the time period between the time that an address of a memory location is specified and the time that data is actually written to the memory location specified by the address. The latency period, measured in clock cycles, arises from the need to perform one or more intermediate operations before the data can be accessed. For example, before data can be written to a memory address, the address must be decoded and the data must be transferred from an external input port to an internal data register.

FIG. 2illustrates an interface of a conventional synchronous RAM device. The address input (ADD) is an n-bit wide bus. The data input (D) is an m-bit wide bus, as is the data output (Q). A read enable (RE) signal enables a data read operation. A write enable (WE) signal enables a data write operation. Clock signals k and k# synchronize the READ/WRITE operations.

FIG. 3illustrates a READ/WRITE timing diagram of a conventional synchronous RAM device, shown with a read latency of 1½ clock cycles and a write latency of 1 clock cycle. Read address A at address input ADD is latched into an address register at time to. Address input ADD is idle at time t1while address A is processed. Similarly, write address B at address input ADD is latched into the address register at time t2and address input ADD is idle at time t3while address B is processed. The sequence is repeated from time t4to time t7for addresses C and D.

Because the data rates are high and the processing is complex, multiple banks of synchronous RAM may be required to manage the data traffic. As a result, many address lines are needed to manage the memory and a correspondingly large number of connection points must be provided on the system processor. This creates several problems. First, the internal design of the processor becomes very difficult, costly and time consuming. Second, the layout of the line-card becomes very difficult, costly and time-consuming. Extra circuit layers may be required to accommodate the required line routing. Each additional layer adds to the manufacturing cost of the board and decreases its reliability.

DETAILED DESCRIPTION

In the following description, numerous specific details are set forth such as examples of specific components, devices, methods, etc., in order to provide a thorough understanding of embodiments of the present invention. It will be apparent, however, to one skilled in the art that these specific details need not be employed to practice embodiments of the present invention. In other instances, well-known materials or methods have not been described in detail in order to avoid unnecessarily obscuring embodiments of the present invention. It should be noted that the “line” or “lines” discussed herein, that connect elements, may be single lines or multiple lines. The term “coupled” as used herein, may mean directly coupled or indirectly coupled through one or more intervening components. It will also be understood by one having ordinary skill in the art that lines and/or other coupling elements may be identified by the nature of the signals they carry (e.g., a “clock line” may implicitly carry a “clock signal”) and that input and output ports may be identified by the nature of the signals they receive or transmit (e.g., “clock input k” may implicitly receive a “clock signal k”).

A system, apparatus and method for address selection are described. In one embodiment, the system includes a processing device that is coupled to a random access memory (RAM) device by a data bus, a system address bus and a pair of clock signal lines. The processing device includes a clock generator that generates a first clock signal and a second clock signal on one or more clock signal lines. The random access memory (RAM) device includes an input address bus coupled to the system address bus. A first storage element with an equal number of inputs and outputs is coupled to the input address bus to receive and store a first memory address segment from the system address bus. A second storage element with an equal number of inputs and outputs is coupled to the input address bus to receive and store a second memory address segment from the system address bus. The first storage element receives and stores the first memory address segment on a first transition of the first clock signal and the second storage element receives and stores the second memory address segment on a first transition of the second clock signal. The first and second storage elements form an internal memory address at their outputs from the first and second memory address segments and propagate the internal memory address on an internal memory address bus.

In one embodiment, the method receives and stores a first and a second memory address segment, during a latency period, on consecutive half cycles of clock signals. An internal memory address formed from the first and second memory address segments is propagated on an internal address bus to an address decoder on a third consecutive half cycle of the clock signals within the latency period.

The described memory addressing may be used to reduce the number of memory address lines in a networking or data communications application, for example, by approximately a factor of two, without reducing the amount of addressable memory or increasing memory access times.

FIG. 4illustrates one embodiment of addressing synchronous RAM in a packet processing system. Packet processing system400may be used in a communication system such as a computer, server, router, switch load balancer, add/drop multiplexer, digital cross-connect, or other piece of communications equipment. Packet processing system400, for example, may be implemented in a line card that links external network connections to each other. Examples of line cards include a switch-fabric card, a time-division multiplexed data card, an Ethernet data card and an optical carrier card. The communication system that hosts the line card may have, for example, a chassis and a backplane with many slots into which one or more line cards may be mounted. The line cards may be removed or inserted to change the number of ports or to support different communication protocols or physical interface devices. Alternatively, packet-processing system400may be implemented in other cards or integrated into other system components.

Packet processing system400may be coupled to network medium412by line414, and to one or more mediums4131–413iby line415. Mediums4131–413imay be similar or dissimilar mediums. Packet processing system400may include physical interface devices410and411coupled to link layer device401by lines405and406, respectively. Link layer device401may include processing device402for processing data packets. Processing device402may be, for example, a network processor, a field programmable gate array (FPGA) or an application specific integrated circuit (ASIC). Alternatively, processing device402may be one or more other processing devices such as a general-purpose processor (e.g., a Motorola PowerPC™ processor or Intel® Pentium® processor) or a special-purpose processor (e.g., a digital signal processor). Processing device402may include clock generator403to generate clock signals. Link layer device401may also include memory array416for storing information (e.g., data packets) and instructions to be executed by processing device402. Memory array416may include memory devices4041–404J. Each of memory devices4041–404Jmay be synchronous random access memory (RAM) devices. Memory devices4041–404Jmay also be either static random access memory devices (SRAM) or dynamic random access memory (DRAM) devices. RAM devices4041–404Jmay be DDR memory devices or QDR™ memory devices. Memory devices4041–404Jmay be coupled to processing device402by clock lines407, system address bus408, and data bus409. Each of memory devices4041–404Jmay be used to store data packets or data and instructions for processing data packets. Processing data may include, for example, processing statistics or routing addresses. Processing instructions may include, for example, queue management instructions or packet routing policy instructions. Each memory device4041–404Jmay include 2naddressable memory locations. In one embodiment, n may be an even number and system address bus408may contain n/2 address lines. In an alternative embodiment, n may be an odd number and system address bus408may include (n+1)/2 address lines. System address bus408may also include one or more chip select lines in addition to address lines. Data bus409may include m bi-directional data lines to carry data to and from memory devices4041–404J. Alternatively, data bus409may include m unidirectional data lines to carry data to memory devices4041–404Jand m unidirectional data lines to carry data from memory devices4041–404J. Memory devices4041–404Jmay be coupled to clock generator403by one or more clock lines407. It should be noted that link layer device401may also include other components and couplings that have not been illustrated, so as not to obscure an understanding of embodiments of the present invention.

In one embodiment, a memory device404may be a synchronous RAM device connected to processing device402, as illustrated inFIG. 5A. Memory device404may have a data input D connected to processing device402by data bus409a. Data bus409amay have m data lines. Memory device404may also have a data output Q connected to processing device402by data bus409b. Data bus409bmay have m lines. Data input D and data output Q may be the same physical interface and data bus409aand data bus409bmay be the same physical data bus. Memory device404may have a read enable input RE connected to processing device402by read enable line417, to enable data to be read from memory device404. Memory device404may also have a write enable input WE connected to processing device402by write enable line418, to enable data to be written to memory device404. Memory device404may also have clock inputs k and k#, connected to processing device402by clock lines407aand407b, to receive clock signals from clock generator403. In one embodiment, clock signal k on clock line407aand clock signal k# on clock line407bmay be complementary clock signals. Memory device404may have an address input ADD, connected to processing device402by system address bus408, to receive memory address segments from processing device402. Memory device404may be an m×2′ memory. In one embodiment, as illustrated inFIG. 5A, n may be an even number and memory device404may have n/2 address inputs. In another embodiment, as illustrated inFIG. 5B, n may be an odd number and memory device404may have (n+1)/2 address inputs. It should be noted that memory device404may also include other inputs and outputs that have not been illustrated so as not to obscure an understanding of embodiments of the present invention.

FIG. 6illustrates one embodiment of address selection in a synchronous RAM device. Synchronous RAM device600may include an address registry and logic circuit665to receive and process memory address segments. Address registry and logic circuit665may include storage element605to store a first address segment, storage element610to store a second address segment, address control logic615to manage clock signals k and k#, and address decoder620. Each of storage elements605and610may be registers or latches or any other type of storage element known in the art. Input address bus601may contain x lines and may receive address segments from system address bus408to transmit to storage elements605and610through buses602and603, respectively. Storage element605may have y inputs and y outputs and each of buses602and604may have y lines. Storage element610may have z inputs and z outputs and each of buses603and606may have z lines. Buses603and606may be coupled to address decoder620through internal address bus607, which may have n lines. Address decoder620may also be coupled to device memory array645by decoded address lines621. Device memory array645may contain 2naddressable memory locations. In one embodiment, n may be an even number, x may be equal to n/2, and both y and z may be equal to n/2 such that y+z may be equal to n. In another embodiment, n may be an odd number, x may be equal to (n+1)/2, and one of y or z may be equal to (n+1)/2 while the other of y or z may be equal to (n−1)/2 such that y+z may be equal to n. Synchronous RAM device600may also include data registry and logic circuit670to receive and process data. Data registry and logic circuit670may include data register630to receive input data from data bus611, and control logic625to manage data register630.

In one exemplary embodiment of address selection for a data read operation, a read enable signal may be issued from processing device402and received by synchronous RAM device600at read enable input RE#. Address control logic615may receive the read enable signal on line608and couple the read enable signal to output buffer660to enable data output. Address control logic615may also control the application of clock signals k and k# to storage elements605and610, and to address decoder620. Clock signals k and k# may be two-state (i.e., binary) signals having periodic state-transitions. Clock signals k and k# may also be complementary signals. On a first state-transition of clock signal k, address control logic615may cause a first read address segment on input address bus601to be stored in storage element605. On a first state-transition of clock signal k#, address control logic615may cause a second read address segment on input address bus602to be stored in storage element610. On a second state-transition of clock signal k, address control logic615may cause an internal read address, formed from the first and second read address segments, to be transmitted on internal address bus607to address decoder620. Address decoder620may send a decoded memory address to memory array645where the contents of the memory location specified by the internal address are retrieved and transported to data output Q by way of sense amps650, output register655, and output buffer660on subsequent transitions of clock signals k & k#. Data output operations are known in the art; accordingly, a detailed description is not provided herein.

In one exemplary embodiment of address selection for a data write operation, a write enable signal may be issued from processing device402and received by synchronous RAM device600at write enable input WE#. Data control logic625may receive the write enable signal on line609and couple the write enable signal to data register630to enable data input. Data control logic615may also control the application of clock signals k and k# to data register630. Address control logic615may receive the write enable signal on line609and control the application of clock signals k and k# to storage elements605and610, and to address decoder620. Clock signals k and k# may be periodic two-state (i.e., binary) signals. Clock signals k and k# may also be complementary signals. On a first state-transition of clock signal k, address control logic615may cause a first write address segment on input address bus601to be stored in storage element605and data control logic625may cause data at input D to be stored in data register630. On a first state-transition of clock signal k#, address control logic615may cause a second write address segment on input address bus602to be stored in storage element610and data in data register630may be transferred to write register635. On a second state-transition of clock signal k, address control logic615may cause an internal write address, formed from the first and second write address segments, to be transmitted on internal address bus607to address decoder620. Address decoder620may send a decoded memory address to memory array645where the memory location specified by the internal write address is filled with the data from write register635through write driver640. Data write operations are known in the art; accordingly, a detailed description is not provided herein. It should be noted that synchronous RAM device600may include additional inputs, outputs, components and couplings that have not been illustrated so as not to obscure understanding of embodiments of the present invention.

FIG. 7Aillustrates one embodiment of address selection for the case of the n number of internal address bus lines being an even number. Storage element605may have n/2 inputs and n/2 outputs, and buses602and604may each have n/2 lines. Storage element610may have n/2 inputs and n/2 outputs, and buses603and606may each have n/2 lines. Internal address bus607may have n lines. Address control logic615couples clock signal k on clock line612to storage element605and address decoder620, and clock signal k# on clock line613to storage element610. Processing device402may assert a read enable signal on line608that is coupled to address control logic615. Alternatively, processing device402may assert a write enable signal on line609that is coupled to address control logic615. In the embodiment, processing device402may transmit the first n/2 bits of an n-bit address to input address bus601at input ADD. On a transition of clock signal k, the first n/2 bits of the n-bit address may be stored in storage device605through buses601and602. Processing device402may then transmit the last n/2 bits of the n-bit address to input address bus601at input ADD. On a transition of clock signal k#, the last n/2 bits of the n-bit address may be stored in storage device610through buses601and603. On the next transition of clock signal k, the first n/2 bits of the n-bit address in storage element605, and the last n/2 bits of the n-bit address in storage element610may be transmitted to address decoder620over buses604and606, respectively, via internal address bus607.

FIG. 7Billustrates one embodiment of address selection for the case of the n number of internal address bus lines being an odd number. Storage element605may have (n+1)/2 inputs and (n+1)/2 outputs, and buses602and604may each have (n+1)/2 lines. Storage element610may have (n−1)/2 inputs and (n−1)/2 outputs, and buses603and606may each have (n−1)/2 lines. Internal address bus607may have n lines. Address control logic615couples clock signal k on clock line612to storage element605and address decoder620, and clock signal k# on clock line613to storage element610. Processing device402may assert a read enable signal on line417that is coupled to address control logic615by line608. Alternatively, processing device402may assert a write enable signal on line418that is coupled to address control logic615by line609. In the embodiment, processing device402may transmit the first (n+1)/2 bits of an n-bit address to input address bus601at input ADD. On a transition of clock signal k, the first (n+1)/2 bits of the n-bit address may be stored in storage device605through buses601and602. Processing device402may then transmit the last (n−1)/2 bits of the n-bit address to input address bus601at input ADD. On a transition of clock signal k#, the last (n−1)/2 bits of the n-bit address may be stored in storage device610through buses601and603. On the next transition of clock signal k, the first (n+1)/2 bits of the n-bit address in storage element605, and the last (n−1)/2 bits of the n-bit address in storage element610may be transmitted to address decoder620over buses604and606, respectively, via internal address bus607.

FIG. 8is a timing diagram illustrating one embodiment of address selection in a synchronous RAM device. In the exemplary embodiment, and with reference also toFIG. 6, the synchronous RAM device may be a burst-of-four QDR™ synchronous SRAM having a READ latency of 1½ clock cycles and a WRITE latency of 1 clock cycle, where times to through t11correspond to alternate rising edges of synchronizing clock signals k and k#.

An exemplary burst-read sequence begins when processing device402asserts a read enable signal801at read enable input RE of synchronous RAM device600. The read enable signal is transmitted to address control logic615by line608. Address control logic615controls the application of clock signals k and k# to storage elements605and610. Address control logic615also controls the application of the read enable signal to output buffer660to enable output port Q. At time t0, the first segment A1of address A is stored in storage element605. At time t1, the second segment A2of address A is stored in storage element610. At time t2, address A is transferred to address decoder620and address A is decoded. Address decoders are known in the art; accordingly, a detailed description is not provided herein. At time t3, the data stored at address (A) is read from device memory array645through sense amps650and latched into output register655where it is available through output buffer660as output data Q(A). Memory arrays, sense amps and buffers are known in the art; accordingly, a detailed description is not provided herein. At time t4, a read address counter (not shown) is incremented, and the data stored at address (A+1) in device memory array645is latched into the output register655where it is available through output buffer660as output data Q(A+1). At time t5, the read address counter is incremented again and the data stored at address (A+2) in device memory array645is latched into the output register655where it is available through output buffer660as output data Q(A+2). At time t6, the read address counter is incremented again and the data stored at address (A+3) in device memory array645is latched into the output register655where it is available through output buffer660as output data Q(A+3). It will be appreciated by one having ordinary skill in the art that a similar sequence of operations may be performed with read address segments C1and C2from time t4through time t6, following the assertion of a read enable signal802by processing device402at time t4, to produce outputs Q(C) through Q(C+3) during time t7through time t10.

An exemplary burst-write operation begins when processing device402asserts a write enable signal803at write enable input WE of synchronous RAM device600. The write enable signal is transmitted to address control logic615and data control logic by lines609. Data control logic625controls the application of clock signals k and k# to data register630. Data control logic625also controls the application of the write enable signal to data register630to enable input port D. At time t2, the first segment B1of address B is stored in storage element605and data at data input D is latched into data register630. At time t3, the second segment B2of address B is stored in storage element610, the data in data register630is pipelined to write register635, and the next data at input D is latched into data register630. At time t4, address B is transferred to address decoder620, address B is decoded and the data in write register635is written to memory address B in device memory array645as D(B) by write driver640. Write drivers are known in the art; accordingly, a detailed description is not provided herein. Also at time t4, the data in data register630is pipelined to write register635and the next data at input D is latched into data register630. At time t5, a write address counter (not shown) is incremented, the data in write register635is written to memory address B+1 in device memory array645as D(B+1) by write driver640. Also at time t5, the data in data register630is pipelined to write register635and the next data at input D is latched into data register630. At time t6, the write address counter is incremented again, the data in write register635is written to memory address B+2 in device memory array645as D(B+2) by write driver640. Also at time t6, the data in data register630is pipelined to write register635. At time t7, the write address counter is incremented again, the data in write register635is written to memory address B+3 in device memory array645as D(B+2) by write driver640. It will be appreciated by one having ordinary skill in the art that a similar sequence of operations may be performed with write address segments D1and D2from time t6through time t8, following the assertion of a write enable signal804by the processing device402at time t6, to write data to addresses (D) through (D+3) during time t8through time t11.

FIG. 9illustrates one embodiment of a method of read/write address selection in a synchronous RAM device. This method provides for address selection during a latency period between the assertion of a read enable or write enable command and the time when a decoded read address or write address is required for memory access. Within the latency period, the memory address is specified in segments and then reconstructed for address decoding. In an exemplary embodiment, synchronous RAM device600receives a read enable signal801, which starts the latency period, step901. First storage element605receives a first address segment A1on input address bus601, step902. The first address segment A1is stored in the first storage element605on a first half-cycle805, step903. Second storage element610receives a second address segment A2on input address bus601, step904. The second address segment A2is stored in the second storage element610on a second half-cycle806, step905. The internal address A is formed from first address segment A1and second address segment A2, step906. Internal address A is provided to address decoder620on a third half cycle807, step907, which terminates the latency period, step908.

It will be appreciated that the method may be applied to write address selection by substituting write enable signal803for read enable signal801, write address segment B1for read address segment A1, half-cycle807for half-cycle805, address segment B2for address segment A2, half-cycle808for half-cycle806, internal address B for internal address A, and half-cycle809for half-cycle807.

Accordingly, embodiments of the invention enable the reduction of the number of memory address lines in a networking or data communications application by approximately a factor of two, without reducing the amount of addressable memory or increasing memory access time.

It should be appreciated that references throughout this specification to “one embodiment” or “an embodiment” means that a particular feature, structure or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Therefore, it is emphasized and should be appreciated that two or more references to “an embodiment” or “one embodiment” or “an alternative embodiment” in various portions of this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures or characteristics may be combined as suitable in one or more embodiments of the invention. In addition, while the invention has been described in terms of several embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described. The embodiments of the invention can be practiced with modification and alteration within the scope of the appended claims. The specification and the drawings are thus to be regarded as illustrative instead of limiting on the invention.