Transposition of two-dimensional arrays using single-buffering

The present embodiments relate to an address generator circuit for addressing a storage circuit. The address generator circuit may generate address signals for read and write access operations at the storage circuit. The write access operation may store a two-dimensional array in the storage circuit and the read access operation may retrieve a transpose of the two-dimensional array from the storage circuit. The address generator circuit may include a status flag generation circuit that generates status flag signals, a modulo adder circuit that receives first and second signals and computes a modulo adder output signal, and an address processing circuit. The address processing circuit may receive the modulo adder output signal from the modulo adder circuit and the plurality of status flag signals from the status flag generation circuit and provide the first and second signals to the modulo adder circuit.

BACKGROUND

The present embodiments relate to integrated circuits and, more particularly, to integrated circuits with circuitry that transposes two-dimensional arrays.

Generating the transpose of a two-dimensional array having M rows and N columns involves swapping the rows of the two-dimensional array (e.g., a matrix A) with the columns of the transpose of the two-dimensional array (e.g., the transposed matrix AT) or the columns of the two-dimensional array (e.g., matrix A) with the rows of the transposed two-dimensional array (e.g., matrix AT). Thus, the transpose of a matrix A with M rows and N columns is a matrix ATwith N rows and M columns. In other words, an element from row i and column j of matrix A (i.e., Aij) becomes an element in row j and column i of the transposed matrix AT(i.e., ATji).

Generating the transpose of a matrix has many applications in linear algebra including the commutativity of scalar multiplications, which is sometimes also referred to as the computation of the dot product, and the computation of the inverse of the two-dimensional array. For example, the dot product (Au).v where A is a matrix with M rows and N columns, u is an N-dimensional vector, and v an M-dimensional vector can be rewritten as u.(ATv) where AThas N rows and M columns and is the transpose of matrix A.

By way of further preliminaries, it will be understood that throughout this disclosure all “data,” “samples,” “items,” “inputs,” “outputs,” “values,” “addresses,”, “difference”, “sum” and/or the like that are referred to are represented by electrical signals that are processed by electronic circuitry. Thus references to “data,” “samples,” “items,” “inputs,” “outputs,” “values,” “addresses,”, “difference”, “sum” and/or the like herein will be understood to always mean “data signals,” “sample signals,” and/or the like, even though the word “signal” or “signals” may not be expressly stated in all instances.

SUMMARY

An address generator circuit for addressing a storage circuit may include a status flag generation circuit, a modulo adder circuit, and an address processing circuit. The status flag generation circuit may generate a plurality of status flag signals. The modulo adder circuit may receive first and second signals and compute a modulo adder output signal based on the first and second signals. The address processing circuit may receive the modulo adder output signal from the modulo adder circuit and the plurality of status flag signals from the status flag generation circuit. Furthermore, the address processing circuit may provide the first and second signals to the modulo adder circuit and generate address signals for read and write access operations of the storage circuit. The write access operation may store a two-dimensional array in the storage circuit and the read access operation may retrieve a transpose of the two-dimensional array from the storage circuit.

It is appreciated that the embodiments described herein can be implemented in numerous ways, such as a process, an apparatus, a system, a device, or a method executed on a processing machine. Several inventive embodiments of the present invention are described below.

In certain embodiments, the address processing circuit may include a delay circuit and an additional storage circuit. The delay circuit may delay the modulo adder output signal by a predetermined time to provide a delayed modulo adder output signal, and the additional storage circuit may store the delayed modulo adder output signal to provide a stored signal.

If desired, the address processing circuit may further include a multiplexer that receives the stored signal from the additional storage circuit, a constant number signal, and an enable signal, selects the first signal among the stored signal and the constant number signal based on the enable signal, and provides the first signal to the modulo adder circuit.

In certain embodiments, the above mentioned address generator circuit may further include a multiplexer that receives the delayed modulo adder output signal, a constant number signal, and a status flag signal of the plurality of status flag signals, selects the second signal among the delayed modulo adder output signal and the constant number signal based on the status flag signal, and provides the second signal to the modulo adder circuit.

In some embodiments, the above mentioned address generator circuit may further include an additional multiplexer that receives the second signal from the aforementioned multiplexer, an additional constant number signal, and an additional status flag signal of the plurality of status flag signals. The additional multiplexer may select the address signals among the second signal and the additional constant number signal based on the additional status flag signal, and provide the address signals for the read and write access operations of the storage circuit.

In some embodiments, the modulo adder circuit may include an adder, a subtractor, a bit extractor, and a multiplexer. The adder may add the first and second signals from the address processing circuit to generate a sum signal. The subtractor may subtract a constant number signal from the sum signal to generate a difference signal. The bit extractor may receive the difference signal and provide a bit extractor output signal that is indicative of whether the difference signal represents a non-negative number. The multiplexer may receive the sum signal, the difference signal, and the bit extractor output signal and select the modulo adder output signal among the sum signal and the difference signal based on the bit extractor output signal.

In some embodiments, the status flag generation circuit may include a modulo counter circuit that receives an enable signal and counts up to a predetermined number to provide a modulo counter output signal.

If desired, the status flag generation circuit may further include first, second, and third comparators. The first comparator may generate a first status flag signal of the plurality of status flag signals based on a first comparison of the modulo counter output signal with a first constant number signal. The second comparator may generate a second status flag signal of the plurality of status flag signals based on a second comparison of the modulo counter output signal with a second constant number signal. The third comparator may generate a third status flag signal of the plurality of status flag signals based on a third comparison of the modulo counter output signal with a third constant number signal.

DETAILED DESCRIPTION

The present embodiments provided herein relate to integrated circuits and, more particularly, to integrated circuits with circuitry that transposes two-dimensional arrays.

Generating the transpose of a two-dimensional array (e.g., a matrix) has many applications in linear algebra including the commutativity of scalar multiplications, which is sometimes also referred to as the computation of the dot product, and the computation of the inverse of the two-dimensional array.

A typical way to implement such two-dimensional array transposition is to use two storage circuits, which may sometimes also be referred to as memory banks. The memory banks may be accessed alternately to store successive complete sets of the data items in the starting order, and the memory bank that is not currently accepting new data items may be addressed to retrieve the previously stored data items in the desired final order.

Requiring two memory banks for this purpose can consume a relatively large amount of memory. Some known techniques that use single-buffering for the transposition of two-dimensional arrays are limited to two-dimensional arrays with M rows and N columns in which M and N are each a power of two (e.g., M=8 and N=16).

Therefore, it may be desirable to generate the transform of a two-dimensional array having numbers of rows and numbers of columns that may be different than powers of two and using single-buffering (i.e., a single storage circuit), which may reduce cost and decrease latency compared to a solution with two memory banks.

It will be recognized by one skilled in the art, that the present exemplary embodiments may be practiced without some or all of these specific details. In other instances, well-known operations have not been described in detail in order not to unnecessarily obscure the present embodiments.

An illustrative embodiment of an integrated circuit101is shown inFIG. 1. Integrated circuit101may have multiple components. These components may include processing circuitry102, storage circuitry110, and input-output circuitry104. Processing circuitry102may include embedded microprocessors, digital signal processors (DSP), microcontrollers, or other processing circuitry.

Input-output circuitry104may include parallel input-output circuitry, differential input-output circuitry, serial data transceiver circuitry, or other input-output circuitry suitable to transmit and receive data. Internal interconnection resources103such as conductive lines and busses may be used to send data from one component to another component or to broadcast data from one component to one or more other components. External interconnection resources105such as conductive lines and busses, optical interconnect infrastructure, or wired and wireless networks with optional intermediate switches may be used to communicate with other devices.

Storage circuitry110may have random-access memory (RAM), read-only memory (ROM), or other addressable memory elements. Storage circuitry110may be a single-port memory, a dual-port memory, a quad-port memory, or have any other arbitrary number of ports. If desired, storage circuitry110may be implemented as a single-port memory with control circuitry that emulates dual-port, quad-port, or other multi-port behavior.

Processing circuitry102may access storage circuitry110by sending read and/or write requests over interconnection resources103to storage circuitry110. In some embodiments, external components may access storage circuitry110via external interconnection resources105, input-output circuitry104, and interconnection resources103. In response to receiving a read request, storage circuitry110may retrieve the requested data during a read access operation and send the retrieved data over interconnection resources103to the requestor. In case of a write request, storage circuitry110may store the received data during a write access operation.

The aforementioned integrated circuit101may include a two-dimensional array transpose circuit. If desired, processing circuitry104and storage circuitry110may implement the two-dimensional array transpose circuit. For example, processing circuitry104may generate read and write address signals for performing read and write access operations at storage circuitry110such that a two-dimensional array is stored in storage circuitry110during a write access operation and the transpose of the two-dimensional array is retrieved during a read access operation.

An illustrative embodiment of a two-dimensional array transpose circuit200is shown inFIG. 2. The two-dimensional array transpose circuit200may receive a two-dimensional array, which is sometimes also referred to as a 2D array, at an input and provide at an output a transpose of the two-dimensional array, which is sometimes also referred to as a transposed 2D array. If desired, the two-dimensional array circuit200may be activated when receiving an enable signal.

As an example, consider the scenario in which two-dimensional array transpose circuit200receives a two-dimensional array with three rows (M=3) with row numbers r being 0, 1, and 2 and five columns (N=5) with column numbers c being 0, 1, 2, 3, and 4.

The position i for each element may be computed by
i=r*N+c(1)

where r is the row number, N is the number of columns, and c is the column number. For example, “1” is in row m2 (i.e., r=2) and the second column (i.e., c=1), with N=5. Thus the position of “1” in the stream is computed as i=2*5+1=11.

The position j for each element may be computed by
j=r+c*M(2)

where r is the row number, c is the column number, and M is the number of rows of the original two-dimensional array (not the transposed two-dimensional array). For example, “l” was in row m2 (i.e., r=2) and the second column (i.e., c=1) of the original two-dimensional array with M=3. Thus, the position of “l” in the transposed stream is computed as j=2+1*3=5.

The above observed relationship between linearization of the two-dimensional array and linearization of the transposed two-dimensional array may be generalized. For example, multiplying equation (1) with M leads to
i*M=(r*N+c)*M=r*N*M+c*M(3)

Furthermore, the modulo (M*N−1) multiplication of M with N is equal to one
(M*N)mod(M*N−1)=1  (4)

Combining equations (3) and (4) leads to
(i*M)mod(M*N−1)=(r+c*M)mod(M*N−1)=jmod(M*N−1)  (5)

The last element in the two-dimensional array (i.e., r=M−1, c=N−1) is at position i=(N*M−1) and the last element in the transposed two-dimensional array at position j=(N*M−1).

Thus, a function P(i) that maps from input positions to output positions is defined as:
P(i)=N*M−1, wheni=N*M−1  (6)
P(i)=(i*M)mod(N*M−1), otherwise  (7)

Multiplying equation (2) with N leads to
j*N=(r+c*M)*N=r*N+c*N*M(8)

Combining equations (4) and (8) leads to
(j*N)mod(N*M−1)=(r*N+c)mod(N*M−1)=imod(N*M−1)  (9)

Thus, an inverse function Q(j) to P(i) which maps output positions onto input positions is defined as:
Q(j)=N*M−1, whenj=N*M−1  (10)
Q(j)=(j*N)mod(N*M−1), otherwise  (11)

An illustrative embodiment of the two-dimensional array transpose circuit200ofFIG. 2is shown inFIG. 3. The two-dimensional array transpose circuit may include storage circuit300and address generator circuit301. Storage circuit300may receive a two-dimensional array and address signals from address generator circuit301and store the two-dimensional array during a write access operation. Storage circuit300may receive address signals from address generator circuit301to generate a transpose of the stored two-dimensional arrays by retrieving the stored two-dimensional array from storage circuit300during a read access operation. In some embodiments, storage circuit300may perform a read access operation for the kthblock using the write address generated using Qk( ) and read the kthblock back using the read address generated using Qk+1( ).

As an example, consider the scenario in which storage circuit300receives blocks 0, 1, and 2 that each include a respective two-dimensional array having three rows (M=3) and five columns (N=5). For example, the 0thblock may include the first two-dimensional array with a first row m0 (i.e., r=0) with elements (a0, b0, c0, d0, e0), a second row m1 (i.e., r=1) with elements (f0, g0, h0, i0, j0), and a third row m2 (i.e., r=2) with elements (k0, l0, m0, n0, o0).

If desired, address generator circuit301may generate write and read addresses according to equations (14) and (15).

For example, for block 0, address generator circuit301may generate for each respective position of the stream the following respective addresses in storage circuit300:

TABLE 1Write addresses for block 0I01234567891011121314Q0(i)01234567891011121314

Thus, storage circuit300may store the first two-dimensional array of block 0 at the following addresses:

TABLE 2Storage circuit contents at respective addresses afterthe write access operation of block 001234567891011121314a0b0c0dOe0f0g0h0i0j0k0l0m0n0o0

For example, the element at position i=3 (i.e., d0) may be stored at address Q0(3)=3, and the element at position i=7 (i.e., h0) may be stored at address Q0(7)=7.

Based on equations (14) and (15), address generator circuit301may generate for each respective position of the stream the following respective addresses Q1(i)=Q1(j) for write and read access operations at storage circuit300:

TABLE 3Write addresses for block 1 and readaddresses for block 0i, j01234567891011121314Q1( )05101611271238134914

Thus, performing a read access operation at storage circuit300to retrieve block 0 may produce the following output stream:

TABLE 4Output stream after the read access operation of block 001234567891011121314a0f0k0b0g0l0c0h0m0d0i0n0e0j0o0

For example, the element at position j=3 of the output stream (i.e., b0) may be retrieved from address Q1(3)=1 of storage circuit300, and the element at position j=7 of the output stream (i.e., h0) may be retrieved from address Q1(7)=7.

Interpreting every three successive elements of the output stream as a row of a two-dimensional array leads to a first row m0 (i.e., r=0) with elements (a0, f0, k0), a second row m1 (i.e., r=1) with elements (b0, g0, l0), a third row m2 (i.e., r=2) with elements (c0, h0, m0), a fourth row m3 (i.e., r=3) with elements (d0, i0, n0), and a fifth row m4 (i.e., r=4) with elements (e0, j0, o0), which is the transpose of the first two-dimensional array.

After having performed the read access operation of block 0, storage circuit300may store the second two-dimensional array of block 1 at the addresses shown in TABLE 3.

TABLE 5Storage circuit contents at respective addresses afterthe write access operation of block 101234567891011121314a1d1g1j1m1b1e1h1k1n1c1f1i1l1o1

For example, the element in the input stream at position i=3 (i.e., d1) may be stored at address Q1(3)=1 and the element at position i=7 (i.e., h1) may be stored at address Q1(7)=7.

Based on equations (14) and (15), address generator circuit301may generate for each respective position of the stream the following respective addresses Q2(i)=Q2(j) for write and read access operations at storage circuit300:

TABLE 6Write addresses for block 2 and readaddresses of block 1i, j01234567891011121314Q2( )01185213107411296314

Thus, performing a read access operation at storage circuit300for block 1 may produce the following output stream:

TABLE 7Output stream after the read access operation of block 101234567891011121314a1f1k1b1g1l1c1h1m1d1i1n1e1j1o1

For example, the element at position j=3 of the output stream (i.e., b1) may be retrieved from address Q2(3)=5 of storage circuit300, and the element at position j=7 of the output stream (i.e., h1) may be retrieved from address Q2(7)=7.

Interpreting every three successive elements of the output stream as a row of a two-dimensional array leads to a first row m0 (i.e., r=0) with elements (a1, f1, k1), a second row m1 (i.e., r=1) with elements (b1, g1, l1), a third row m2 (i.e., r=2) with elements (c1, h1, m1), a fourth row m3 (i.e., r=3) with elements (d1, i1, n1), and a fifth row m4 (i.e., r=4) with elements (e1, j1, o1), which is the transpose of the second two-dimensional array.

After having performed the read access operation of block 1, storage circuit300may store the third two-dimensional array of block 2 at the addresses shown in TABLE 6.

TABLE 8Storage circuit contents at respective addresses afterthe write access operation of block 201234567891011121314a2j2e2n2i2d2m2h2c2l2g2b2k2f2o2

For example, the element in the input stream at position i=3 (i.e., d2) may be stored at address Q2(3)=5 and the element at position i=7 (i.e., h2) may be stored at address Q2(7)=7.

Storage circuit300may include single-port memory circuitry or multi-port memory circuitry such as dual-port circuitry or quad-port circuitry, just to name a few. If desired, storage circuit300may implement read-before-write behavior. In other words, a read access operation may retrieve the content of the storage circuit300from a location based on a predetermined address before new content is stored at that same location during a write access operation. In some embodiments, registers or other storage circuitry may be coupled with storage circuit300to enable read-before-write behavior.

As another example, consider the scenario in which read and write operations are scheduled at a same clocking event. In this scenario, storage circuit300may include separate clock connections for the read clock and the write clock. If desired, the write clock may be delayed compared to the read clock, thereby enabling read-before-write behavior even though a read and a write access operation are scheduled at the same clocking event.

The delay between the read event and the write event may be comparatively small since read and write access operations occur at the same addresses in storage circuit300. For example, after reading back the first seven items of block 1 (i.e., a1, g1, b1, k1 c1, f1, and l1) from storage circuit300, the eight unread items (i.e., d1, j1, m1, e1, h1, n1, i1 and o1) occupy the following memory locations:

TABLE 9Unread items of block 1 in the storage circuit01234567891011121314d1j1m1e1h1n1i1o1

After the first 7 items of storage circuit300have been read back, the first 7 items of the next stream may perform write access operations to the same memory locations:

TABLE 10Written items of block 2 in the storage circuit01234567891011121314a2e2d2c2g2b2f2

Thus, the overall buffer contents may be:

TABLE 11Storage circuit contents during read and write accessoperations01234567891011121314a2d1e2j1m1d2e1h1c2n1g2b2i1f2o1

An illustrative embodiment of the address generator circuit301ofFIG. 3is shown inFIG. 4. The address generator circuit301may include a status flag generation circuit402, a modulo adder circuit400, and an address processing circuit401. The status flag generation circuit402may receive an enable signal, generate status flag signals based on the enable signal, and send the status flag signals to the address processing circuit401.

The address processing circuit401may receive the enable signal, a modulo adder output signal from the modulo adder output circuit400, and send first and second signals to the modulo adder output circuit400.

If desired, the address processing circuit may send the address signals for the read and write access operations to storage circuit300. If desired, the address signals for the write access operation may enable the storage of a two-dimensional array in storage circuit300and the signals for the read access operation may retrieve a transpose of the two-dimensional array from storage circuit300.

Modulo adder output circuit400may perform a modulo addition of the first and second signals to generate the modulo adder output signal. Modulo adder circuit400may be implemented using any modulo adder architecture. For example, modulo adder circuit400may perform a modulo X addition by adding the first and second signals to generate a sum and recursively subtracting X from the sum as long as the result is greater than or equal to X.

An illustrative embodiment of a modulo adder circuit such as modulo adder circuit400is shown inFIG. 5. As shown, the modulo adder circuit may include adder500, subtractor501, bit extractor502, constant number storage504and multiplexer503.

Adder500may include logic gates and implement any adder architecture such as a ripple-carry adder, a carry-save adder, a carry-lookahead adder, just to name a few. As shown, adder500may receive first and second signals at inputs510and520and provide a sum signal to subtractor501and multiplexer503of the modulo adder circuit.

Constant number storage504may include any memory architecture capable of storing a constant number. For example, constant number storage504may include multiple registers where every register stores a bit of the constant number. If desired, constant number storage504may include read-only memory (ROM), random-access memory (RAM), or any other memory capable of storing a constant number.

Constant number storage504may store a predetermined constant number. For example, constant number storage504may store M*N−1 where M is the number of rows and N the number of columns of a two-dimensional array. If desired, constant number storage504may be omitted and the constant number may be supplied through an input port to the modulo adder circuit.

Subtractor501may generate a difference of the sum signal and the constant number. If desired, constant number storage504may store the two's complement of the constant number that is to be subtracted from the sum and subtractor501may be replaced by an adder.

Multiplexer503may receive the difference signal from subtractor501, the sum signal from adder500and a bit extractor output signal from bit extractor502and select between the sum signal and the difference signal based on the bit extractor output signal.

Bit extractor502may receive the difference from subtractor501and provide a bit extractor output signal. If desired, bit extractor output signal may be logical ‘1’ when the difference signal represents a negative number and logical ‘0’ otherwise.

Multiplexer503may select the sum signal if the difference is a negative number (e.g., if constant number504is predetermined to be M*N−1 and the sum is smaller than M*N−1). Multiplexer503may select the difference signal, when bit extractor502receives a non-negative number.

Multiplexer503may generate at output530a modulo adder output signal. In particular, consider the scenario in which constant number504is M*N−1 with M=3 rows and N=5 columns. In this scenario, M*N−1 is equal to 14.

Thus, as long as the sum of the first and second signals (510,520) is smaller than 14, multiplexer503will select the sum of the first and second signals as the modulo adder output signal. If the sum of the first and second signal is greater or equal than 14, multiplexer503may select the difference from subtractor501as the modulo adder output signal.

As shown, the modulo adder output signal is smaller than (M*N−1) as long as the sum of the first and second signals (510,520) is smaller than 2*(M*N−1)−1. The sum of first and second signals may be designed to be smaller than 2*(M*N−1)−1.

For example, the loop from modulo adder circuit400through address processing circuit401back to modulo adder circuit400may ensure that at least one of the first and second signals (510,520) is smaller than M*N−1, and thus the sum is always smaller that 2*(M*N−1)−1.

Alternatively, a pre-processing step may ensure that the first and second signals are smaller than M*N−1. For example, in modulo arithmetic
(X+Y)mod(Z)=(Xmod(Z)+Ymod(Z))mod(Z)  (16)

Thus, generating the first signal (e.g., signal X′) from a signal X by performing a modulo (M*N−1) operation on signal X (i.e., X′=X mod(M*N−1)) and generating the second signal (e.g., signal Y′) from signal Y by performing a modulo (M*N−1) operation on signal Y (i.e., Y′=Y mod(M*N−1)) ensures that the first and second signal are both smaller than (M*N−1).

An illustrative embodiment of an address processing circuit such as address processing circuit401is shown inFIG. 6. The address processing circuit may receive an enable signal, a modulo adder output signal from a modulo adder circuit such as modulo adder circuit400ofFIG. 4at input620, and status flag signals from a status flag generation circuit such as status flag generation circuit402ofFIG. 4at inputs630,660,670, and680.

The address processing circuit may generate an address signal for performing read and/or write access operations at a storage circuit such as storage circuit300ofFIG. 3as well as first and second signals for a modulo adder circuit such as modulo adder circuit400ofFIG. 4at outputs640and650, respectively.

The address processing circuit may include delay circuit600, multiplexers604,605, and607, constant number storage circuits602and606, and latches601and603that may implement an additional storage circuit. As shown, latches601and603are initialized to store the number one.

As shown inFIG. 6, delay circuit600may receive the modulo adder output signal via input620, delay the modulo adder output signal, and provide the delayed modulo adder signal to latch601and multiplexer605. If desired, delay circuit600may delay the modulo adder output signal by one or more clock cycles.

Constant number storage602and606may each store a respective constant number. For example, constant number storage602and606may both store a ‘0’. In this example, constant number storage602and604may be combined into a single constant number storage that is coupled to both multiplexers604and605.

Multiplexer604may receive the constant number signal from constant number storage602, a stored signal from latch603and an enable signal. Multiplexer604may select between the stored signal and the constant number signal based on the enable signal and thereby generate the first signal at output640of the address processing circuit.

The constant number stored in constant number storage602may be used to initialize the first signal of the modulo adder circuit. If desired, the constant number may be zero, which is selected as long as the additional storage circuit is disabled (i.e., the enable signal is ‘0’).

Multiplexer605may receive the delayed modulo adder output signal from delay circuit600, the constant number signal from constant storage circuit606and a status flag signal from a status flag generation circuit such as status flag generation circuit402ofFIG. 4at input670.

Multiplexer605may select between the delayed modulo adder output signal and the constant number signal based on the status flag signal and provide the selected signal as the second signal to the modulo adder circuit and to multiplexer607.

Multiplexer607may receive the second signal from multiplexer605, a status flag signal from a status flag generation circuit such as status flag generation circuit402ofFIG. 4at input680and a constant number signal via input630. The multiplexer607may select between the second signal and the constant number signal based on the status flag signal and provide the selected signal as the address signals for the read and write access operations of the storage circuit.

An illustrative embodiment of a status flag generation circuit such as status flag generation circuit402ofFIG. 4is shown inFIG. 7. As shown, the status flag generation circuit may receive an enable signal and generate status flag signals at outputs760,770,780, and790.

If desired, the status flag generation circuit may include modulo counter700, constant number storage circuits702,704, and706, and comparators701,703, and705. Modulo counter700may receive an enable signal, count up to a predetermined number, and output a modulo counter output signal. For example, to generate the transpose of a two-dimensional array with M=3 rows and N=5 columns, modulo counter700may implement a modulo (M*N) counter that repeatedly counts from 0 to 14, and outputs the respective modulo counter output signal as long as the enable signal is asserted.

If desired, modulo counter700may increment the modulo counter output signal based on a clock signal. For example, modulo counter700may increment the modulo counter output signal once every clock cycle. As another example, modulo counter700may increment the modulo counter output signal once every p clock cycles where p can be a predetermined number.

As shown inFIG. 7, comparators701,703, and705may receive the modulo counter output signal and a respective constant number signal from respective constant number storage circuits702,704, and706and generate respective status flag signals at outputs760,770, and780based on the comparison of the modulo counter output signal with the respective constant number signal.

For example, constant number storage702may store a constant number that corresponds to the number of columns N of the two-dimensional array (e.g., N=5 as in the example above). Thus, comparator701may provide a status flag signal ‘0’ when the modulo counter output signal is different than N and a status flag signal ‘1’ when the modulo counter output signal is equal to N.

Constant number storage704may store a zero. Thus, comparator703may provide a status flag signal ‘0’ when the modulo counter output signal is greater than zero and a status flag signal ‘1’ when the modulo counter output signal is equal to zero.

Constant number storage706may store a constant number that corresponds to the product (M*N−1), where M is the number of rows and N the number of columns of the two-dimensional array (e.g., M=3 and N=5 as in the example above). The status flag generation circuit may provide this constant number at output790, and comparator705may provide a status flag signal ‘0’ when the modulo counter output signal is different than (M*N−1) and a status flag signal ‘1’ when the modulo counter output signal is equal to (M*N−1).

Consider the scenario of the above example with M=3 and N=5. Consider further that modulo counter700implements a (M*N) counter, that outputs760,770,780, and790of the status flag generation circuit are coupled to inputs660,670,680, and630of the address generation circuit ofFIG. 6, respectively, that outputs640and650and input620of the address generation circuit ofFIG. 6are coupled to inputs510and520and output530of the modulo adder circuit ofFIG. 5, respectively, that latches601and603ofFIG. 6are initialized to one, and that constant number storage504,602,606,702,704, and706store (M*N−1), zero, zero, N, zero, and (M*N−1), respectively.

In this scenario, the different components of the modulo adder circuit ofFIG. 5, the address processing circuit ofFIG. 6, and the status flag generation circuit ofFIG. 7may generate the following signals:

TABLE 12Signals in the address generation circuitcycle0123456789101112131470001234567891011121314601111111555555555603111111111111111605012345678910111213050012345678910111213141501−13−12−11−10−9−8−7−6−5−4−3−2−10−136041234567891011121301600?12345678910111213060701234567891011121314cycle1516171819202122232425262728297000123456789101112131460155555511111111111111111160355555555555555560505101611271238134905005101561116712158131891419501−9−41−8−32−5−23−3−14−5056045101611271238134905600151016112712381349060705101611271238134914cycle303132333435363738394041424344700012345678910111213146011111111111111313131313131313136031111111111111111111111111111116050118521310741129630500112219161324211815122320171411501−3852−110741−29630−360411852131074112963011600511852131074112963060701185213107411296314

With multiplexer607of the address processing circuit ofFIG. 6generating the addresses that are used to perform write access operations at storage circuit300ofFIG. 3for blocks 0, 1, and 2, respectively, and read access operations at storage circuit300ofFIG. 3for blocks 0 and 1, respectively (see also TABLES 1, 3, and 6).

FIG. 8is a diagram of a flow chart showing illustrative steps for operating an address generator circuit, such as address generator circuit301ofFIG. 3to generate read and write address signals for a storage circuit such as storage circuit300in accordance with an embodiment. During step810, the address generator circuit may receive an enable signal. For example, the status flag generation circuit402and the address processing circuit401ofFIG. 4may receive an enable signal.

During step820, the address generator circuit301may generate a plurality of status flag signals. For example, the status flag generation circuit ofFIG. 7may generate first, second, and third status flag signals at outputs760,770, and780of the status flag generation circuit.

During step830, the address generator circuit may perform a modulo addition of first and second signals to compute a modulo adder output signal. For example, the modulo adder circuit ofFIG. 5may receive the first and second signal at inputs510,520and generate a modulo adder output signal at an output530of the modulo adder circuit.

During step840, the address generator circuit may generate read and write address signals for performing read and write access operations at the storage circuit based on the enable signal, the plurality of status flag signals, and the modulo adder output signal. For example, in the two-dimensional array transpose circuit ofFIG. 3, the write access operation may store a two-dimensional array in storage circuit300and the read access operation may retrieve a transpose of the two-dimensional array from the storage circuit300.

The method and apparatus described herein may be incorporated into any suitable electronic device or system of electronic devices. For example, the method and apparatus may be incorporated into numerous types of devices such as microprocessors or other integrated circuits. Exemplary integrated circuits include programmable array logic (PAL), programmable logic arrays (PLAs), field programmable logic arrays (FPGAs), electrically programmable logic devices (EPLDs), electrically erasable programmable logic devices (EEPLDs), logic cell arrays (LCAs), field programmable gate arrays (FPGAs), coarse-grained reconfigurable architectures (CGRAs), application specific standard products (ASSPs), application specific integrated circuits (ASICs), just to name a few.

The integrated circuit described herein may be part of a data processing system that includes one or more of the following components; a processor; memory; I/O circuitry; and peripheral devices. The data processing system can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, or any suitable other application where the advantage of generating a transpose of a two-dimensional array is desirable.

The integrated circuit may be configured to perform a variety of different logic functions. For example, the integrated circuit may be configured as a processor or controller that works in cooperation with a system processor. The integrated circuit may also be used as an arbiter for arbitrating access to a shared resource in the data processing system. In yet another example, the integrated circuit may be configured as an interface between a processor and one of the other components in the system. In one embodiment, the integrated circuit may be one of the families of devices owned by the assignee.