Fault tolerant hard disk array controller

Claim 1

A fault tolerant memory array control system for controlling data accesses to and from a host bus and a memory array of discrete bulk memory units, organized by physical channel index and physical rank index, wherein bulk memory units with the same rank index are of a similar type, and bulk memory units with the same channel index share a common channel data bus, the memory array control system comprising: (a) a controller system bus for control and data communication between elements of the memory array control system; (b) a microprocessor controller coupled to the controller system bus for performing logical control of the memory array control system elements, the microprocessor controller comprising: (i) a microprocessor for executing operating control programs and configuration control programs comprising: (aa) a translation program for optimally translating address data of a host logical data access request to the memory array into a minimal set of memory array physical address and length data for accessing appropriate bulk memory units; (bb) a scheduling program for determining and executing an optimal sequence of steps by which to execute a queued set of memory array access requests, including parallel access when possible, by optimizing a prescribed performance function criterion; (cc) a crippled operation program for using module redundancy and parity data encoding methods for sustaining system operation after a bulk memory failure; and (dd) a computer kernel control means for coordinating all system functions and resources; and (ii) an interrupt controller connected to the microprocessor for accepting and prioritizing externally generated interrupt requests from the host system bus interface and from a drive channel controller; c) a host system bus interface coupled to the controller bus; (d) a set of more than one drive channel controller, each controller of the set for coupling to a unique common channel data bus for selecting a bulk memory unit, and for control of and data transfers to and from the selected bulk memory unit sharing the common channel data bus; a data path unit comprising; (i) a data path selector, having an output and more than one input, each input connected to one of the set of drive channel controllers for selecting a drive channel; and (ii) a data path coupled to the host system bus interface and connected to the data path selector output for coupling the selected drive channel to the host computer system bus; and (f) translation means, controlled by the translation program, for translating logical access address data to a physical array access address data set for an array of physical channels, using a RAID format, the logical access address data described by a starting block address, and a block length parameter indicating the number of contiguous blocks to be accessed, and producing a set of channel indices, a set of channel starting addresses, and a set of channel transfer length parameters, indicating the number of contiguous blocks to be accessed for each physical rank, for each channel, for producing a set of physical access address data requiring a minimal set of access commands.

Claim 19

A method for translating logical access address data to a logical and physical drive access address data set for a logical array of bulk memories having C logical data channels, one parity channel, and a plurality of logical rank levels, the array using a RAID-4 block striping data format, the logical access address data described by a starting block address, n, and a block length parameter, N, indicating the number of contiguous blocks to be accessed, and producing a set of channel indices, {m i }, a set of channel starting addresses, {s mi (j)}, and a set of channel transfer length parameters, {x i (j)}, indicating the length of access for each rank, p j , involved in the access for each channel, for producing an optimal set of logical drive access addresses requiring a minimal set of access commands, the method comprises: (a) mapping the logical block address information given as the logical starting block, n, and the number of contiguous blocks, N, to be accessed into a set of logical channel indices, {m i }, by use of the following relationship: m.sub.i =(n+i) mod C, where 0≦i≦C-1 is an index representing the order of accessing the channel corresponding to the value of m i ; (b) identifying the first logical drive, D mi ,pi, on each channel involved in the access, the coordinate parameters (m i ,p i ), satisfying the following conditions: M.sub.pi ≦(n+i)/C≦M.sub.pi+1, where M pi =Σ j=0 pi-1 B j , p i is a logical rank index, and B j is the number of blocks in rank j logical drive; (c) computing a set of starting logical drive block addresses for the first logical drive, D mi ,pi, on each channel, {s mi (0)}, as follows: s.sub.mi (0)=(((n+i)-m.sub.i)/C)-M.sub.pi ; (d) computing the number of blocks to be accessed, x i (0), for each logical drive, D mi ,pi, as follows: x.sub.i (0)=min { N/C +σ((N mod C)-i), B.sub.pi -s.sub.mi (0)}, where σ(·)=1 for ((N mod C)-i)>0, and σ(·)=0 otherwise; (e) testing to determine if additional higher logical ranks are involved in the access by evaluating if: x.sub.i (0)< N/C +σ((N mod C)-i); (f) setting the starting logical drive block address in logical drive D mi ,pi+1, s mi (1)=0, if x i (0) satisfies the condition of step (e); (g) computing the number of data blocks in logical drive D mi ,pi+1, x 1 (1), if x i (0) satisfies the condition of step (e), using the following expression: x.sub.i (1)=max{0,min{ N/C +σ((N mod C)-i)-x.sub.i (0), B.sub.(pi+1) }}; (h) testing to determine if additional higher logical ranks are involved in the access by evaluating if x i (j)>0, where ##EQU29## so that if x i (j)>0, x i (j) represents the number of blocks in logical drive D mi ,pi+j involved in the access and s mi (j)=0 represents the starting logical drive block address; (i) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, to determine physical rank and physical channel; and (j) adding a physical address of the logical drive's block number 0 to the logical starting block address, s mi (j) to determine a physical starting block address.

Claim 20

A method for translating logical access address data to a logical and physical drive access address data set for a logical array of bulk memories having C logical data channels, one parity channel, and a plurality of logical rank levels, the array using a RAID-4 block striping data format, the logical access address data described by a starting block address, n, and a block length parameter, N, indicating the number of contiguous blocks to be accessed, and producing a set of channel indices, {m i }, a set of channel starting addresses, {s mi (j)}, and a set of channel transfer length parameters, {x i (j)}, indicating the length of access for each rank, p j , involved in the access for each channel, for producing an optimal set of logical drive access addresses requiring a minimal set of access commands, the method comprises: (a) mapping the logical block address information given as the logical starting block, n, and the number of contiguous blocks, N, to be accessed into a set of logical channel indices, {m i }, by use of the following relationship: m.sub.i =(n+i) mod C, where 0≦i≦C-1 is an index representing the order of accessing the channel corresponding to the value of m i ; (b) identifying the first logical drive, D mi ,pi, on each channel involved in the access, the coordinate parameters (m i ,p i ), satisfying the following conditions: M.sub.pi ≦(n+i)/C≦M.sub.pi+1, where M pi =Σ j=0 pi-1 B j , p i is a logical rank index, and B j is the number of blocks in rank j logical drive; (c) computing a set of starting logical drive block addresses for the first logical drive, D mi ,pi, on each channel, {s mi (0)}, as follows: s.sub.mi (0)=(((n+i)-m.sub.i)/C)-M.sub.pi ; (d) computing the number of blocks to be accessed, x i (0), for each logical drive, D mi ,pi, as follows: x.sub.i (0)=min { N/C +σ((N mod C)-i), B.sub.pi -s.sub.mi (0)}, where σ(·)=1 for ((N mod C)-i)>0, and σ(·)=0 otherwise; (e) testing to determine if additional higher logical ranks are involved in the access by evaluating if: x.sub.i (0)< N/C +σ((N mod C)-i); (f) setting the starting logical drive block address in logical drive D mi ,pi+1, s mi (1)=0, if x i (0) satisfies the condition of step (e); (g) computing the number of data blocks in logical drive D mi ,pi+1, x 1 (1), if x i (0) satisfies the condition of step (e), using the following expression: x.sub.i (1)=max{0,min{ N/C +σ((N mod C)-i)-x.sub.i (0), B.sub.(pi+1) }}; (h) testing to determine if additional higher logical ranks are involved in the access by evaluating if x i (j)>0, where ##EQU29## so that if x i (j)>0, x i (j) represents the number of blocks in logical drive D mi ,pi+j involved in the access and s mi (j)=0 represents the starting logical drive block address; (i) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, to determine physical rank and physical channel; and (j) adding a physical address of the logical drive's block number 0 to the logical starting block address, s mi (j) to determine a physical starting block address.

Claim 21

A method for translating logical address access data to a logical and physical drive access data set, for accommodating an array of C logical data channels using a RAID-1 partitioned mirrored data format, the logical access address data described by a starting block address, n, and a logical block length parameter, N, indicating the number of contiguous blocks to be accessed, and producing a set of channel indices, {m i }, a set of logical drive starting addresses, {s mi (j)}, and a set of logical drive transfer length parameters, {x i (j)}, indicating the number of contiguous blocks to be accessed for each logical rank, p j , for each channel, for producing a set of logical drive access address data requiring a minimal set of access commands, the partitioned memory having a first set of channel and rank coordinates, (m,p), for a first partitioned section of memory, and a second set (m', p') for a second partitioned section of memory, the translation method comprising: (a) mapping the logical block address information given as the logical starting block, n, and the number of contiguous blocks, N, to be accessed into a set of logical channel indices, {m i }, by use of the following relationship: m.sub.i =(n+i) mod C, where 0≦i≦C-1 is an index representing the order of accessing the channel corresponding to the value of m i ; (b) identifying the first logical drive, D mi ,pi, on each channel involved in the access, the coordinate parameters (m i ,p i ), satisfying the following conditions: M.sub.pi ≦(n+i)/C≦M.sub.pi+1, where M pi =Σ j=0 pi-1 B j , p i is a logical rank index, and B j is the number of blocks in a rank j logical drive; (c) computing a set of starting logical drive block addresses for the first logical drive, D mi ,pi, on each channel, {s mi (0)}, as follows: s.sub.mi (0)=(((n+i)-m.sub.i)/C)-M.sub.pi ; (d) computing the number of blocks to be accessed, x i (0), for each logical drive, D mi ,pi, as follows: x.sub.i (0)=min{ N/C +σ((N mod C)-i), B.sub.pi -s.sub.mi (0)}, where σ(·)=1 for ((N mod C)-i)>0, and σ(·)=0 otherwise; (e) testing to determine if additional higher logical ranks are involved in the access by evaluating if: x.sub.i (0)< N/C +σ((N mod C)-i); (f) setting the starting logical drive block address in logical drive D mi ,pi+1, s mi (1)=0, if x i (0) satisfies the condition of step (e); (g) computing the number of data blocks in logical drive D mi ,pi+1, x i (1), if x i (0) satisfies the condition of step (e), using the following expression: x.sub.i (1)=max{0,min{ N/C +σ((N mod C)-i)-x.sub.i (0), B.sub.(pi+1) }}; (h) testing to determine if additional higher logical ranks are involved in the access by evaluating if x i (j)>0, where ##EQU30## so that if x i (j)>0, x i (j) represents the number of blocks in logical drive D mi ,pi+j involved in the access and s mi (j)=0 represents the starting logical drive block address; (i) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, D mk ,pk, to determine physical rank and physical channel; and (j) adding a physical address of the logical drive's block number 0 to the logical starting block address, s mi (j) to determine a physical starting block address; and for the second memory section, use means (a)-(j) as indicated above, using coordinate system (m', p').

Claim 22

A method for translating logical address access data to a logical and physical drive access data set, for accommodating an array of C logical data channels using a RAID-1 partitioned mirrored data format, the logical access address data described by a starting block address, n, and a logical block length parameter, N, indicating the number of contiguous blocks to be accessed, and producing a set of channel indices, {m i }, a set of logical drive starting addresses, {s mi (j)}, and a set of logical drive transfer length parameters, {x i (j)}, indicating the number of contiguous blocks to be accessed for each logical rank, p j , for each channel, for producing a set of logical drive access address data requiring a minimal set of access commands, the partitioned memory having a first set of channel and rank coordinates, (m,p), for a first partitioned section of memory, and a second set (m', p') for a second partitioned section of memory, the translation method comprising: (a) mapping the logical block address information given as the logical starting block, n, and the number of contiguous blocks, N, to be accessed into a set of logical channel indices, {m i }, by use of the following relationship: m.sub.i =(n+i) mod C, where 0≦i≦C-1 is an index representing the order of accessing the channel corresponding to the value of m i ; (b) identifying the first logical drive, D mi ,pi, on each channel involved in the access, the coordinate parameters (m i ,p i ), satisfying the following conditions: M.sub.pi ≦(n+i)/C≦M.sub.pi+1, where M pi =Σ j=0 pi-1 B j , p i is a logical rank index, and B j is the number of blocks in a rank j logical drive; (c) computing a set of starting logical drive block addresses for the first logical drive, D mi ,pi, on each channel, {s mi (0)}, as follows: s.sub.mi (0)=(((n+i)-m.sub.i)/C)-M.sub.pi ; (d) computing the number of blocks to be accessed, x i (0), for each logical drive, D mi ,pi, as follows: x.sub.i (0)=min{ N/C +σ((N mod C)-i), B.sub.pi -s.sub.mi (0)}, where σ(·)=1 for ((N mod C)-i)>0, and σ(·)=0 otherwise; (e) testing to determine if additional higher logical ranks are involved in the access by evaluating if: x.sub.i (0)< N/C +σ((N mod C)-i); (f) setting the starting logical drive block address in logical drive D mi ,pi+1, s mi (1)=0, if x i (0) satisfies the condition of step (e); (g) computing the number of data blocks in logical drive D mi ,pi+1, x i (1), if x i (0) satisfies the condition of step (e), using the following expression: x.sub.i (1)=max{0,min{ N/C +σ((N mod C)-i)-x.sub.i (0), B.sub.(pi+1) }}; (h) testing to determine if additional higher logical ranks are involved in the access by evaluating if x i (j)>0, where ##EQU30## so that if x i (j)>0, x i (j) represents the number of blocks in logical drive D mi ,pi+j involved in the access and s mi (j)=0 represents the starting logical drive block address; (i) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, D mk ,pk, to determine physical rank and physical channel; and (j) adding a physical address of the logical drive's block number 0 to the logical starting block address, s mi (j) to determine a physical starting block address; and for the second memory section, use means (a)-(j) as indicated above, using coordinate system (m', p').

Claim 23

A method for translating logical address access data to a logical and physical drive access data set, for accommodating an array of C logical data channels using a RAID-3 format, the logical access address data described by a starting block address, n, and a logical block length parameter, N, indicating the number of contiguous blocks to be accessed, and for producing a set of logical drive starting addresses, {s(j)), and a set of logical drive transfer length parameters, {x(j)}, indicating the number of contiguous blocks to be accessed at logical ranks, {p j }, for each channel, for producing a set of logical drive access address data requiring a minimal set of access commands, the method comprising: (a) mapping the logical block address information given as the logical starting block, n, and the number of contiguous blocks to be accessed, N, into a rank index p 0 , that represents the first rank of logical drives involved in the data access and satisfies the condition: M.sub.p0 ≦n≦M.sub.p0+1, where M p0 =Σ k=0 p0-1 B k ', M 0 =0 and B k ' is the number of blocks in all logical drives in rank k; (b) computing a starting logical drive block address, s(0) , on each channel, as follows: s(0)=n-M.sub.p0 ; (c) computing the number of blocks to be accessed, x(0), for each channel as follows: x(0)=min{N, B.sub.p -s(0)}; (d) testing to determine if additional higher logical ranks are involved in the access by evaluating if: x(0)<N, which, if satisfied, indicates that the rank p 0 +1 logical drives are involved with starting addresses of s(1)=0; (e) computing the number of data blocks to be accessed in each logical drive, if x(0) satisfies the condition of step (d), by: x(1)=max{0,min{(N-x(0)), B.sub.(p0+1) }}; (f) testing to determine if additional higher logical ranks are involved in the access by evaluating if x(j)>0, where ##EQU31## so that if x(j)>0, x(j) represents the number of blocks, beginning at address s(j)=0, in all memory units of rank p j =p 0 +j; (g) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, D mk ,pk, to determine physical rank and physical channel; and (h) adding the physical address of the logical drive's block number 0 to the logical starting block address, s(k) to determine physical starting block address.

Claim 24

A method for translating logical address access data to a logical and physical drive access data set, for accommodating an array of C logical data channels using a RAID-3 format, the logical access address data described by a starting block address, n, and a logical block length parameter, N, indicating the number of contiguous blocks to be accessed, and for producing a set of logical drive starting addresses, {s(j)), and a set of logical drive transfer length parameters, {x(j)}, indicating the number of contiguous blocks to be accessed at logical ranks, {p j }, for each channel, for producing a set of logical drive access address data requiring a minimal set of access commands, the method comprising: (a) mapping the logical block address information given as the logical starting block, n, and the number of contiguous blocks to be accessed, N, into a rank index p 0 , that represents the first rank of logical drives involved in the data access and satisfies the condition: M.sub.p0 ≦n≦M.sub.p0+1, where M p0 =Σ k=0 p0-1 B k ', M 0 =0 and B k ' is the number of blocks in all logical drives in rank k; (b) computing a starting logical drive block address, s(0) , on each channel, as follows: s(0)=n-M.sub.p0 ; (c) computing the number of blocks to be accessed, x(0), for each channel as follows: x(0)=min{N, B.sub.p -s(0)}; (d) testing to determine if additional higher logical ranks are involved in the access by evaluating if: x(0)<N, which, if satisfied, indicates that the rank p 0 +1 logical drives are involved with starting addresses of s(1)=0; (e) computing the number of data blocks to be accessed in each logical drive, if x(0) satisfies the condition of step (d), by: x(1)=max{0,min{(N-x(0)), B.sub.(p0+1) }}; (f) testing to determine if additional higher logical ranks are involved in the access by evaluating if x(j)>0, where ##EQU31## so that if x(j)>0, x(j) represents the number of blocks, beginning at address s(j)=0, in all memory units of rank p j =p 0 +j; (g) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, D mk ,pk, to determine physical rank and physical channel; and (h) adding the physical address of the logical drive's block number 0 to the logical starting block address, s(k) to determine physical starting block address.

Claim 25

A method for translating logical address access data to a logical and physical drive access data set, for accommodating an array of C logical data channels using a RAID-5 block striping format with distributed parity for allowing parallel access operations, the distributed parity blocks located at reserved logical block addresses, n j , where n j satisfies a constraint condition, n j mod C 2 =j(C+1) for j=0, 1, 2, . . . , C-1, the logical access address data described by a starting block address, n, and a logical block length parameter, N, indicating the number of contiguous blocks to be accessed, and producing a set of channel indices, {m i }, a set of logical drive starting addresses, {s mi (j)}, and a set of logical drive transfer length parameters, {x i (j)}, indicating the number of contiguous blocks to be accessed for each logical rank, p j , for each channel, for producing a set of logical access address data requiring a minimal set of access commands, the method comprising: (a) defining a modified logical block address index, n', and a modified length index, N', satisfying the following conditions: n'=n+P(n) and N'=N+P(n+N-1)-P(n), where ##EQU32## (b) mapping the modified logical block address information given as the logical starting block, n', and the number of contiguous blocks to be accessed, N', into a set of logical channel indices, {m i }, by use of the following relationship: m.sub.i =(n'+i) mod C, where 0≦i≦C-1 is an index representing the order of accessing the channel corresponding to the value of m i ; (c) identifying the first logical drive, D mi ,pi, on each channel involved in the access, the coordinate parameters (m i ,p i ), satisfying the following conditions: M.sub.pi ≦(n'+i)/C≦M.sub.pi+1, where M pi =Σ j+0 pi-1 B j , p i is a logical rank index, and B j is the number of blocks in a rank j logical drive; (d) computing a set of starting logical drive block addresses for the first logical drive, D mi ,pi, on each channel, {s mi (0)}, as follows: s.sub.mi (0)=(((n'+i)-m.sub.i)/C)-M.sub.pi ; (e) computing the number of blocks to be accessed, x i (0), for each logical drive, D mi ,pi, as follows: x.sub.i (0)=min { N'/C +σ((N' mod C)-i), B.sub.pi -s.sub.mi (0)}, where σ(·)=1 for ((N' mod C)-i)>0, and σ(·)=0 otherwise. (f) testing to determine if additional higher logical ranks are involved in the access by evaluating if: x.sub.i (0)< N'/C +σ((N' mod C)-i); (g) setting the starting logical drive block address in logical drive D.sub.mi,pi+1, s.sub.mi (1)=0; (h) computing the number of data blocks in logical drive D mi ,pi+1, x i (1), if x i (0) satisfies the condition of step (f), using the following expression: x.sub.i (1)=max{0,min{ N'/C +σ((N' mod C)-i)-x.sub.i (0), B.sub.pi+1) }}; (i) testing to determine if additional higher logical ranks are involved the access by evaluating if x i (j)>0, where ##EQU33## so that if x i (j)>0, x i (j) represents the number of blocks in logical drive D mi ,pi+j involved in the access and s mi (j)=0 represents the starting logical drive block address; (j) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, D mk ,pk, to determine physical rank and physical channel; and (k) adding the physical address of the logical drive's block number 0 to the logical starting block address, s i (j), to determine physical starting block address.

Claim 26

A method for translating logical address access data to a logical and physical drive access data set, for accommodating an array of C logical data channels using a RAID-5 block striping format with distributed parity for allowing parallel access operations, the distributed parity blocks located at reserved logical block addresses, n j , where n j satisfies a constraint condition, n j mod C 2 =j(C+1) for j=0, 1, 2, . . . , C-1, the logical access address data described by a starting block address, n, and a logical block length parameter, N, indicating the number of contiguous blocks to be accessed, and producing a set of channel indices, {m i }, a set of logical drive starting addresses, {s mi (j)}, and a set of logical drive transfer length parameters, {x i (j)}, indicating the number of contiguous blocks to be accessed for each logical rank, p j , for each channel, for producing a set of logical access address data requiring a minimal set of access commands, the method comprising: (a) defining a modified logical block address index, n', and a modified length index, N', satisfying the following conditions: n'=n+P(n) and N'=N+P(n+N-1)-P(n), where ##EQU32## (b) mapping the modified logical block address information given as the logical starting block, n', and the number of contiguous blocks to be accessed, N', into a set of logical channel indices, {m i }, by use of the following relationship: m.sub.i =(n'+i) mod C, where 0≦i≦C-1 is an index representing the order of accessing the channel corresponding to the value of m i ; (c) identifying the first logical drive, D mi ,pi, on each channel involved in the access, the coordinate parameters (m i ,p i ), satisfying the following conditions: M.sub.pi ≦(n'+i)/C≦M.sub.pi+1, where M pi =Σ j+0 pi-1 B j , p i is a logical rank index, and B j is the number of blocks in a rank j logical drive; (d) computing a set of starting logical drive block addresses for the first logical drive, D mi ,pi, on each channel, {s mi (0)}, as follows: s.sub.mi (0)=(((n'+i)-m.sub.i)/C)-M.sub.pi ; (e) computing the number of blocks to be accessed, x i (0), for each logical drive, D mi ,pi, as follows: x.sub.i (0)=min { N'/C +σ((N' mod C)-i), B.sub.pi -s.sub.mi (0)}, where σ(·)=1 for ((N' mod C)-i)>0, and σ(·)=0 otherwise. (f) testing to determine if additional higher logical ranks are involved in the access by evaluating if: x.sub.i (0)< N'/C +σ((N' mod C)-i); (g) setting the starting logical drive block address in logical drive D.sub.mi,pi+1, s.sub.mi (1)=0; (h) computing the number of data blocks in logical drive D mi ,pi+1, x i (1), if x i (0) satisfies the condition of step (f), using the following expression: x.sub.i (1)=max{0,min{ N'/C +σ((N' mod C)-i)-x.sub.i (0), B.sub.pi+1) }}; (i) testing to determine if additional higher logical ranks are involved the access by evaluating if x i (j)>0, where ##EQU33## so that if x i (j)>0, x i (j) represents the number of blocks in logical drive D mi ,pi+j involved in the access and s mi (j)=0 represents the starting logical drive block address; (j) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, D mk ,pk, to determine physical rank and physical channel; and (k) adding the physical address of the logical drive's block number 0 to the logical starting block address, s i (j), to determine physical starting block address.

Claim 28

A method for translating logical address access data to a logical and physical drive access data set, for accommodating an array of C logical data channels, using a two dimensional RAID-2D5 block striping format with distributed parity for allowing parallel access operations, the distributed parity blocks located at reserved logical block addresses, n j , where n j satisfies a constraint condition, n j mod C 2 =j(C+1) for j=0, 1, 2, . . . , C-1, the logical access address data described by a starting block address, n, and a logical block length parameter, N, indicating the number of contiguous blocks to be accessed, and producing an intermediate set of logical channel indices, {m i }, a final set of logical channel indices {m i '}, a set of logical drive starting addresses, {s mi (j)}, and a set of logical drive transfer length parameters, {x i (j)}, indicating the number of contiguous blocks to be accessed for each logical rank, p j , for each channel, for producing a set of logical access address data requiring a minimal set of access commands, the translation method comprising: (a) defining a modified channel parameter, C', and a modified rank parameter R', satisfying the following conditions: C'=C·R and R'=1; (b) defining a modified logical block address index, n', and a modified length index, N', satisfying the following conditions: n'=n+P(n) and N'=N+P(n+N-1)-P(n), where ##EQU34## (c) mapping the modified logical block address information given as the logical starting block, n', and the number of contiguous blocks to be accessed, N', into an intermediate set of logical channel indices, {m i }, by use of the following relationship: m.sub.i =(n'+i) mod C', where 0≦i≦C'-1 is an index representing the order of accessing the channel corresponding to the value of m i ; (d) identifying the logical drive, D mi ,0, on each channel involved in the access, the coordinate parameters (m i , 0), satisfying the following conditions: ≦ (n'+i)/C'≦B.sub.0, where B 0 is the number of blocks each logical drive; (e) computing a set of starting logical drive block addresses for the logical drive, D mi ,0, on each channel, {s mi (0), as follows: s.sub.mi (0)=(((n'+i)-m.sub.i)/C')-B.sub.0 ; (f) computing the number of blocks to be accessed, x i (0), for each logical drive, D mi ,0, as follows: x.sub.i (0)=min{ N'/C' +σ((N' mod C')-i), B.sub.0 -s.sub.mi (0)}, where σ(·)=1 for ((N' mod C')-i)>0, and σ(·)=0 otherwise; (g) computing a new modified set of channel parameters, {m i '}, and a modified set of rank parameters, {p i '}, satisfying the following conditions: m.sub.i '=m.sub.i mod C and p.sub.i '= m.sub.i /C ; (h) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, D m .sbsb.k ' ,p.sbsb.k ' , to determine physical rank and physical channel; and (i) adding the physical address of the logical drive's block number 0 to the logical starting block address, s i (j), of each logical drive to determine physical starting block address.

Claim 29

A method for translating logical address access data to a logical and physical drive access data set, for accommodating an array of C logical data channels, using a two dimensional RAID-2D5 block striping format with distributed parity for allowing parallel access operations, the distributed parity blocks located at reserved logical block addresses, n j , where n j satisfies a constraint condition, n j mod C 2 =j(C+1) for j=0, 1, 2, . . . , C-1, the logical access address data described by a starting block address, n, and a logical block length parameter, N, indicating the number of contiguous blocks to be accessed, and producing an intermediate set of logical channel indices, {m i }, a final set of logical channel indices {m i '}, a set of logical drive starting addresses, {s mi (j)}, and a set of logical drive transfer length parameters, {x i (j)}, indicating the number of contiguous blocks to be accessed for each logical rank, p j , for each channel, for producing a set of logical access address data requiring a minimal set of access commands, the translation method comprising: (a) defining a modified channel parameter, C', and a modified rank parameter R', satisfying the following conditions: C'=C·R and R'=1; (b) defining a modified logical block address index, n', and a modified length index, N', satisfying the following conditions: n'=n+P(n) and N'=N+P(n+N-1)-P(n), where ##EQU34## (c) mapping the modified logical block address information given as the logical starting block, n', and the number of contiguous blocks to be accessed, N', into an intermediate set of logical channel indices, {m i }, by use of the following relationship: m.sub.i =(n'+i) mod C', where 0≦i≦C'-1 is an index representing the order of accessing the channel corresponding to the value of m i ; (d) identifying the logical drive, D mi ,0, on each channel involved in the access, the coordinate parameters (m i , 0), satisfying the following conditions: ≦ (n'+i)/C'≦B.sub.0, where B 0 is the number of blocks each logical drive; (e) computing a set of starting logical drive block addresses for the logical drive, D mi ,0, on each channel, {s mi (0), as follows: s.sub.mi (0)=(((n'+i)-m.sub.i)/C')-B.sub.0 ; (f) computing the number of blocks to be accessed, x i (0), for each logical drive, D mi ,0, as follows: x.sub.i (0)=min{ N'/C' +σ((N' mod C')-i), B.sub.0 -s.sub.mi (0)}, where σ(·)=1 for ((N' mod C')-i)>0, and σ(·)=0 otherwise; (g) computing a new modified set of channel parameters, {m i '}, and a modified set of rank parameters, {p i '}, satisfying the following conditions: m.sub.i '=m.sub.i mod C and p.sub.i '= m.sub.i /C ; (h) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, D m .sbsb.k ' ,p.sbsb.k ' , to determine physical rank and physical channel; and (i) adding the physical address of the logical drive's block number 0 to the logical starting block address, s i (j), of each logical drive to determine physical starting block address.

Claim 30

A method for translating logical address access data to a logical and physical drive access data set, for accommodating an array of C logical data channels, using a two dimensional block striping RAID-2D4 format, the logical access address data described by a starting block address, n, and a logical block length parameter, N, indicating the number of contiguous blocks to be accessed, and producing an intermediate set of logical channel indices, {m i }, a final set of logical channel indices, {m i '}, a set of logical drive starting addresses, {s mi (j)}, and a set of logical drive transfer length parameters, {x i (j)}, indicating the number of contiguous blocks to be accessed for each logical rank, p j , for each channel, for producing a set of logical access address data requiring a minimal set of access commands, the translation method comprising: (a) defining a modified channel parameter, C', and a modified rank parameter R', satisfying the following conditions: C'=C·R and R'=1; (b) mapping the logical block address information given as the logical starting block, n, and the number of contiguous blocks, N, to be accessed into an intermediate set of logical channel indices, {m i }, by use of the following relationship: m.sub.i =(n+i) mod C', where 0≦i≦C'-1 is an index representing the order of accessing the channel corresponding to the value of m i ; (c) identifying the logical drive, D mi ,0, on each channel involved in the access, the coordinate parameters (m i , 0), satisfying the following conditions: 0≦(n+i)/C'≦B.sub.0, where B 0 is the number of blocks in each logical drive; (d) computing a set of starting logical drive block addresses for the first logical drive, D mi ,0, on each channel, {s mi (0)}, as follows: s.sub.mi (0)=(((n+i)-m.sub.i)/C')-B.sub.0 ; (e) computing the number of blocks to be accessed, x i (0), for each logical drive, D mi ,0, as follows: x.sub.i (0)=min{ N/C' +σ((N mod C')-i), B.sub.0 -s.sub.mi (0)}, where σ(·)=1 for ((N mod C')-i)>0, and σ(·)=0 otherwise; (f) computing a new modified set of channel parameters, {m i '56 , and a modified set of rank parameters, {p i '}, satisfying the following conditions: m.sub.i '=m.sub.i mod C and p.sub.i '= m.sub.i /C ; (g) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, D m .sbsb.k ' ,p.sub..sbsb.k ' , to determine physical rank and physical channel; and (h) adding the physical address of the logical drive's block number 0 to the logical starting block address, s i (j), of each logical drive to determine physical starting block address.

Claim 31

A method for translating logical address access data to a logical and physical drive access data set, for accommodating an array of C logical data channels, using a two dimensional block striping RAID-2D4 format, the logical access address data described by a starting block address, n, and a logical block length parameter, N, indicating the number of contiguous blocks to be accessed, and producing an intermediate set of logical channel indices, {m i }, a final set of logical channel indices, {m i '}, a set of logical drive starting addresses, {s mi (j)}, and a set of logical drive transfer length parameters, {x i (j)}, indicating the number of contiguous blocks to be accessed for each logical rank, p j , for each channel, for producing a set of logical access address data requiring a minimal set of access commands, the translation method comprising: (a) defining a modified channel parameter, C', and a modified rank parameter R', satisfying the following conditions: C'=C·R and R'=1; (b) mapping the logical block address information given as the logical starting block, n, and the number of contiguous blocks, N, to be accessed into an intermediate set of logical channel indices, {m i }, by use of the following relationship: m.sub.i =(n+i) mod C', where 0≦i≦C'-1 is an index representing the order of accessing the channel corresponding to the value of m i ; (c) identifying the logical drive, D mi ,0, on each channel involved in the access, the coordinate parameters (m i , 0), satisfying the following conditions: 0≦(n+i)/C'≦B.sub.0, where B 0 is the number of blocks in each logical drive; (d) computing a set of starting logical drive block addresses for the first logical drive, D mi ,0, on each channel, {s mi (0)}, as follows: s.sub.mi (0)=(((n+i)-m.sub.i)/C')-B.sub.0 ; (e) computing the number of blocks to be accessed, x i (0), for each logical drive, D mi ,0, as follows: x.sub.i (0)=min{ N/C' +σ((N mod C')-i), B.sub.0 -s.sub.mi (0)}, where σ(·)=1 for ((N mod C')-i)>0, and σ(·)=0 otherwise; (f) computing a new modified set of channel parameters, {m i '56 , and a modified set of rank parameters, {p i '}, satisfying the following conditions: m.sub.i '=m.sub.i mod C and p.sub.i '= m.sub.i /C ; (g) executing a user specified mapping of logical channel and logical rank to physical channel and physical rank of logical drive, D m .sbsb.k ' ,p.sub..sbsb.k ' , to determine physical rank and physical channel; and (h) adding the physical address of the logical drive's block number 0 to the logical starting block address, s i (j), of each logical drive to determine physical starting block address.

Claim 32

A method for accessing a memory array of C physical channels that reduces latency by optimizing parallel access to a memory array of discrete bulk memory units organized by physical channel index and physical rank index, wherein bulk memory units with the same rank are of a similar type, and bulk memory units with the same channel index share a common channel data bus, the method comprising: (a) receiving an outside request for array memory access, the access identified by a logical memory address and data block length; (b) converting logical addresses to physical addresses; (c) forming a memory access queue of all requests received but not executed; (d) computing the minimum latency order of accessing the queued requests as follows: (i) prescribing a cost function, D, representative of the latency for all possible sequential orders of accessing the queued set of m host access requests to the memory array, where ##EQU35## a k is a C×1 resource vector for queued request k with binary elements (0, 1), where a 1 indicates that a particular memory array channel is used by queued request k, n 0 +N 0 is an initial address corresponding to a last array logical address used to access memory, n k is a memory array logical address to the k th queued memory access request, N k is a memory array block size of the k th queued memory access request, x ij is a binary valued coefficient, {0,1}, which indicates that an i th queued memory access is followed by a j th queued memory access when x ij =1, and 2 -adj is a binary parameter scaling factor in which d j is a count of the number of time the j th access request has been rescheduled without execution and a is a constant scaling parameter, (ii) minimizing cost function D subject to a set of conditions as follows: ##EQU36## (iii) ordering the set of m coefficients, {x ij }, obtained in step (d)(ii), beginning with x 0b1 , and proceeding to the right as follows: x.sub.0b1 x.sub.b1b2 x.sub.b2b3 . . . x.sub.bm-1bm, so that each j th index of each coefficient, x ij , becomes an i tk index of a next right adjacent coefficient, (iv) arranging the order of b-subscripts of the m coefficients in ascending order, b 1 b 2 b 3 . . . b m , for indicating the left to right sequence for ordering the m queued access requests indexed 1, 2, . . . , m, so that, by following the order of subscripts, an optimized sequence for accessing yields an access sequence with minimum latency; (e) sorting the requests in the memory access queue in the minimum latency order obtained in step (d); and (f) accessing the memory array in accordance with the order of the memory access queue of step (e).

Claim 33

A method for accessing a memory array of C physical channels that reduces latency by optimizing parallel access to a memory array of discrete bulk memory units organized by physical channel index and physical rank index, wherein bulk memory units with the same rank are of a similar type, and bulk memory units with the same channel index share a common channel data bus, the method comprising: (a) receiving an outside request for array memory access, the access identified by a logical memory address and data block length; (b) converting logical addresses to physical addresses; (c) forming a memory access queue of all requests received but not executed; (d) computing the minimum latency order of accessing the queued requests as follows: (i) prescribing a cost function, D, representative of the latency for all possible sequential orders of accessing the queued set of m host access requests to the memory array, where ##EQU35## a k is a C×1 resource vector for queued request k with binary elements (0, 1), where a 1 indicates that a particular memory array channel is used by queued request k, n 0 +N 0 is an initial address corresponding to a last array logical address used to access memory, n k is a memory array logical address to the k th queued memory access request, N k is a memory array block size of the k th queued memory access request, x ij is a binary valued coefficient, {0,1}, which indicates that an i th queued memory access is followed by a j th queued memory access when x ij =1, and 2 -adj is a binary parameter scaling factor in which d j is a count of the number of time the j th access request has been rescheduled without execution and a is a constant scaling parameter, (ii) minimizing cost function D subject to a set of conditions as follows: ##EQU36## (iii) ordering the set of m coefficients, {x ij }, obtained in step (d)(ii), beginning with x 0b1 , and proceeding to the right as follows: x.sub.0b1 x.sub.b1b2 x.sub.b2b3 . . . x.sub.bm-1bm, so that each j th index of each coefficient, x ij , becomes an i tk index of a next right adjacent coefficient, (iv) arranging the order of b-subscripts of the m coefficients in ascending order, b 1 b 2 b 3 . . . b m , for indicating the left to right sequence for ordering the m queued access requests indexed 1, 2, . . . , m, so that, by following the order of subscripts, an optimized sequence for accessing yields an access sequence with minimum latency; (e) sorting the requests in the memory access queue in the minimum latency order obtained in step (d); and (f) accessing the memory array in accordance with the order of the memory access queue of step (e).