US 5,367,669 A · Fault tolerant hard disk array controller

A fault tolerant memory array control system for controlling data accesses to and from a host system bus and a memory array of discrete bulk memory units, organized by channel index and rank index, wherein bulk memory units with the same rank index are of a similar type and capacity, 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 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 computer 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;
(e) 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.

13 more elements

A method for translating logical access address data to a physical array access address data set for an array of bulk memories having C channels and a plurality of rank levels, the array using a RAID-0 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.sub.i }, a set of channel starting addresses, {s.sub.m.sbsb.i }, and a set of channel transfer length parameters, {x.sub.i (j)}, indicating the length of access for each rank, p.sub.ij, involved in the access for each channel, for producing an optimal set of physical 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 to be accessed, N, into a set of channel indices, {m.sub.i }, by use of the following relationship:
m.sub.i =(n+i) mod C
where 0.ltoreq.i.ltoreq.C-1 is an index representing the order of accessing the channel corresponding to the value of m.sub.i ;
(b) identifying the first drive, D.sub.m.sbsb.i.spsb.,p.sbsb.i, involved in the access, the coordinate parameters (m.sub.i, p.sub.i), satisfying the following conditions:
M.sub.p.sbsb.i .ltoreq.(n+i)/C<M.sub.p.sbsb.i.spsb.+1
where ##EQU24## p.sub.i is a rank index, and B.sub.k is the number of blocks in rank k;
(c) computing a set of starting physical block addresses for each channel, {s.sub.m.sbsb.i }, as follows:
s.sub.m.sbsb.i =((n+i)-m.sub.i)/C-M.sub.p.sbsb.i ;
(d) computing the number of blocks to be accessed, x.sub.i (0), for each channel, m.sub.i, as follows:
x.sub.i (0)=min{([N/C]+.sigma.(N mod C-i)),(B.sub.p.sbsb.i -s.sub.m.sbsb.i)},
where .sigma.(.cndot.)=1 for (N mod C-i)>0, and .sigma.(.cndot.)=0 otherwise;
(e) testing to determine if additional higher ranks are involved in the access by evaluating if:
x.sub.i (0)<[N/C]+.sigma.(N mod C-i);
(f) if x.sub.i (0) satisfies the condition of step (e), computing the number of data blocks in drive D.sub.m.sbsb.i.spsb.,p.sbsb.i.spsb.+1, x.sub.i (1), using the following expression:
x.sub.i (1)=max{0,min{[N/C]+.sigma.(N mod C-i)-x.sub.i (0), B.sub.p.sbsb.i.spsb.+1 }};
and
(g) testing to determine if additional higher ranks are involved in the access by evaluating if x.sub.i (j)>0, where ##STR12## so that if x.sub.i (j)>0, x.sub.i (j) represents the number of blocks in drive D.sub.m.sbsb.i.spsb.,p.sbsb.i.spsb.+j involved in the access.

14 more elements

A method for translating logical access address data to a physical array access address data set for an array of bulk memories having C channels and a plurality of rank levels, the array using a RAID-1 partitioned mirrored 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.sub.i }, a set of channel starting addresses, {s.sub.m.sbsb.i }, and a set of channel transfer length parameters, {x.sub.i (j)}, indicating the number of contiguous blocks to be accessed for each rank, p.sub.j, and for each channel, for producing a set of physical access address data requiring a minimal set of access commands, the partitioned mirrored 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 method comprises:

(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 set of channel indices, {m.sub.i }, by use of the following relationship:
m.sub.i =(n+i) mod C
where 0.ltoreq.i.ltoreq.C-1 is an index representing the order of accessing the channel corresponding to the value of m.sub.i ;
(b) identifying the first drive, D.sub.m.sbsb.i.spsb.,p.sbsb.i, involved in the access, the coordinate parameters (m.sub.i, p.sub.i), satisfying the following conditions:
M.sub.p.sbsb.i .ltoreq.(n+i)/C<M.sub.p.sbsb.i.spsb.+1
where ##EQU25## p.sub.i is a rank index, and B.sub.k is the number of blocks in rank k;
(c) computing a set of starting physical block addresses for each channel, {s.sub.m.sbsb.i }, as follows:
s.sub.m.sbsb.i =((n+i)-m.sub.i)/C-M.sub.p.sbsb.i ;
(d) computing the number of blocks to be accessed, x.sub.i (0), for each channel, m.sub.i, as follows:
x.sub.i (0)=min{([N/C]+.sigma.(N mod C-i)),(B.sub.p.sbsb.i -s.sub.m.sbsb.i)},
where .sigma.(.cndot.)=1 for (N mod C-i)>0, and .sigma.(.cndot.)=0 otherwise;
(e) testing to determine if additional higher ranks are involved in the access by evaluating if:
x.sub.i (0)<[N/C]+.sigma.(N mod C-i);
(f) if x.sub.i (0) satisfies the condition of step (e), computing the number of data blocks in drive D.sub.m.sbsb.i.spsb.,p.sbsb.+1, x.sub.i (1), using the following expression:
x.sub.i (1)=max{0,min{[N/C]+.sigma.(N mod C-i)-x.sub.i (0), B.sub.p.sbsb.i.spsb.+1 }};
and
(g) testing to determine if additional higher ranks are involved in the access by evaluating if x.sub.i (j)>0, where ##STR13## so that if x.sub.i (j)>0, x.sub.i (j) represents the number of blocks in drive D.sub.m.sbsb.i.spsb.,p.sbsb.i.spsb.+j involved in the access;
and for the second memory section, use steps (a)-(g) above using coordinate system (m', p').

15 more elements

A method for translating logical access address data to a physical array access address data set for an array of bulk memories having C channels and a plurality of rank levels, using a RAID-5 block striping format with distributed parity for allowing parallel access operations, the distributed parity blocks located at reserved logical block address set, {n.sub.j }, where {n.sub.j } satisfies a constraint condition, n.sub.j mod C.sup.2 =j(C+1) for j=0,1,2, . . . , C-1, the physical array access address data set includes a set of channel indices, {m.sub.i }, a set of channel starting addresses, {s.sub.m.sbsb.i }, and a set of channel transfer length parameters, {x.sub.i (j)}, indicating the number of blocks in rank j and channel m.sub.i that are involved in the access, for producing a set of physical access address data requiring a minimal set of access commands, the method comprises:

(a) defining a modified logical block address index, n, and a modified length index, N, satisfying the following conditions:
n'=n+P(n)
N'=N+P(n+N-1)-P(n)
where ##STR14## (b) 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 set of channel indices, {m.sub.i }, by use of the following relationship:
m.sub.i =(n'+i) mod C
where 0.ltoreq.i.ltoreq.C-1 is an index representing the order of accessing the channel corresponding to the value of m.sub.i ;
(c) identifying the first drive, D.sub.m.sbsb.i.spsb.,p.sbsb.i, involved in the access, the coordinate parameters (m.sub.i, p.sub.i), satisfying the following conditions:
M.sub.p.sbsb.i .ltoreq.(n'+i)/C<M.sub.p.sbsb.i.spsb.+1
where ##EQU28## p.sub.i is a rank index, and B.sub.k is the number of blocks in rank k;
(d) computing a set of starting physical block addresses for each channel, {s.sub.m.sbsb.s }, as follows:
s.sub.m.sbsb.i =((n'+i)-m.sub.i)/C-M.sub.p.sbsb.i ;
(e) computing the number of blocks to be accessed, x.sub.i (0), for each channel, m.sub.i, as follows:
x.sub.i (0)=min{([N'/C]+.sigma.(N' mod C-i)),(B.sub.p.sbsb.i -s.sub.m.sbsb.i)},
where .sigma.(.cndot.)=1 for (N' mod C-i)>0, and .sigma.(.cndot.)=0 otherwise;
(f) testing to determine if additional higher ranks are involved in the access by evaluating if:
x.sub.i (0)<[N'/C]+.sigma.(N' mod C-i);
(g) if x.sub.i (0) satisfies the condition of step (e), computing the number of data blocks in drive D.sub.m.sbsb.i.spsb.,p.sbsb.i.spsb.+1, x.sub.i (1), using the following expression:
x.sub.i (1)=max{0,min{[N'/C]+.sigma.(N' mod C-i) -x.sub.i (0),B.sub.p.sbsb.i.spsb.+1 }};
and
(h) testing to determine if additional higher ranks are involved in the access by evaluating if x.sub.i (j)>0, where ##STR15## so that if x.sub.i (j)>0, x.sub.i (j) represents the number of blocks in drive D.sub.m.sbsb.i.spsb.,p.sbsb.i.spsb.+j involved in the access.

17 more elements

A method for accessing a memory array that reduces latency by optimizing parallel access to a memory array of discrete bulk memory units organized by channel index and rank index, wherein bulk memory units with the same rank are of a similar type and capacity, 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 virtual memory address and data block length;
(b) converting virtual address 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;
(e) sorting the requests in the memory access queue in the minimum latency order obtained in step (d);
(f) determining channel bus resource usage of the queued requests and identifying queued access requests that can be done in parallel;
(g) sorting the memory access queue to reflect parallel accesses that may be accomplished while the order of step (e) is otherwise preserved by executing allowable lower order accesses in parallel with higher order accesses;
and
(h) accessing the memory array in accordance with the order of the memory access queue of step (g).

6 more elements

Fault tolerant hard disk array controller

Life of this patent

Fault tolerant hard disk array controller

Life of this patent

Abstract

Claims32