1. An apparatus for outputting an input data block comprising a plurality of bits as an output data block with at least one puncturing or with at least one repetition of at least one bit, where the input data block contains a plurality of input data words having a respective plurality of bits, and the output data block contains output data words associated with the input data words the apparatus comprising:
an association unit for associating the bits in an input data word (11; 31) with the bits in the associated output data word on the basis of an alterable puncturing or repetition pattern the association unit being a hardware circuit which is designed to execute both puncturing and repetitive coding, and the association unit having a plurality of association elements which each have a logic input and a logic output for associating a bit in an input data word with one or no bit in the associated output data word;
a control unit for producing the puncturing or repetition pattern on the basis of prescribed puncturing or repetition information; and
a first address generation unit for producing first addresses for the logic outputs of the association elements for respective association with a bit in the output data word on the basis of the puncturing pattern and for producing first addresses for the logic inputs (pi(w)) of the association elements for respective association with a bit in the input data word on the basis of the repetition pattern.
2. The apparatus as claimed in claim 1, further comprising:
a second address generation unit for producing second addresses for the logic inputs of the association elements for continuous association with a respective bit in the input data word when the apparatus is operated as a puncturing apparatus, and for producing second addresses for the logic outputs of the association elements for continuous association with a respective bit in the output data word when the apparatus is operated as a repetition apparatus.
3. The apparatus as claimed in claim 1, further comprising:
an input memory for buffer-storing at least one input data word, the input memory comprising a plurality of registers which are respectively designed to store a bit, and
an output memory for buffer-storing at least one output data word the output memory comprising a plurality of registers which are respectively designed to store a bit.
4. The apparatus as claimed in claim 3, further comprising:
a first rewriteable memory connected upstream of the input memory for storing input data blocks, and
a second rewriteable memory connected downstream of the output memory for storing output data blocks.
5. The apparatus as claimed in claim 2, further comprising
a plurality of control units.
6. The apparatus as claimed in claim 2,
wherein the control unit, the first address generation unit and the second address generation unit are each designed as hardware.
7. The apparatus as claimed in claim 5, wherein
the control units produce a puncturing or repetition pattern based on the UMTS standard 3GPP TS 25.212.
8. A method for operating an apparatus for outputting an input data block comprising a plurality of bits as an output data block with at least one puncturing or with at least one repetition of at least one bit, where the input data block contains a plurality of input data words having a respective plurality of bits, and the output data block contains output data words associated with the input data words, the apparatus having an association unit for associating the bits in an input data word with the bits in the associated output data word on the basis of an alterable puncturing or repetition pattern (incw(k)), the association unit being a hardware circuit which is designed to execute both puncturing and repetitive coding, and the association unit having a plurality of association elements (MUXw) which each have a logic input and a logic output for associating a bit in an input data word with one or no bit in the associated output data word, the apparatus having a control unit for producing the puncturing or repetition pattern (incw(k)) on the basis of prescribed puncturing or repetition information, and the apparatus having a first address generation unit for producing first addresses (pdw(k)) for the logic outputs (po(w)) of the association elements (MUXw) for respective association with a bit in the output data word on the basis of the puncturing pattern (incw(k)) and for producing first addresses (pdw(k)-for the logic inputs (pi(w)) of the association elements (MUXw) for respective association with a bit in the input data word on the basis of the repetition pattern (incw(k)), where
the apparatus has Wmax association elements MUXw (w=0, 1, . . . , Wmax-1), and
the input data word has Lmax bits, the method comprising:
operating the apparatus in cycles k (k=0, 1, 2, . . . );
producing Wmax control signals (incw(k)) in each cycle k using the control and the first address generation unit;
producing a first address pdw(k) for each association element MUXw using the first address generation unit;
wherein a first initialization address pdini(k) is used to initialize the cycle k, the first addresses pdw(k) being calculated on the basis of the following recursive rules:
pd0(k)=pdini(k) \u2003\u2003(1)
pdw(k)=(pdw-1(k)+incw-1(k)) mod Lmax \u2003\u2003(2)
pdini(k+1)=(pdWmax-1(k)+incWmax-1(k)) mod Lmax \u2003\u2003(3)
pdini(0)=0 \u2003\u2003(4)
where incw(k)=0 indicates that the bit applied to the input of the association element MUXw needs to be punctured or repeated, and incw(k)=1 indicates that the bit applied to the input of the association element MUXw does not need to be punctured and does not need to be repeated, and where puncturing the bit applied to the input of the association element MUXw involves the logic output (po(w)) of the association element MUXw being disabled.
9. The method as claimed in claim 8, wherein the second address generation unit produces a second address psw(k) in each cycle k for each association element MUXw;
wherein a second initialization address psini(k) is used to initialize the cycle k; and
wherein the second addresses psw(k) are calculated on the basis of the following recursive rules:
ps0(k)=psini(k) \u2003\u2003(5)
psw(k)=(psw-1(k)+1) mod Lmax \u2003\u2003(6)
psini(k+1)=(psWmax-1(k)+1) mod Lmax \u2003\u2003(7)
psini(0)=0 \u2003\u2003(8).
10. The apparatus as claimed in claim 1, further comprising an input memory for buffer-storing at least one input data word, the input memory comprising a plurality of registers which are respectively designed to store a bit.
11. The apparatus as claimed in claim 10, further comprising a first rewriteable memory connected upstream of the input memory for storing input data blocks.
12. The apparatus as claimed in claim 1, further comprising an output memory for buffer-storing at least one output data word, the output memory comprising a plurality of registers which are respectively designed to store a bit.
13. The apparatus as claimed in claim 12, further comprising a second rewriteable memory connected downstream of the output memory for storing output data blocks.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A quality-of-service method for data storage, the method comprising:
prioritizing a plurality of requests for each of a plurality of workloads;
selectively forwarding the requests to a queue according to said prioritizing for maintaining the queue at a target queue depth, wherein completed requests are removed from the queue; and
adjusting the target queue depth in response to a latency statistic for the requests wherein the latency statistic is computed based on a measured difference between an arrival time and a completion time of a plurality of the requests.
2. The method according to claim 1, wherein said prioritizing comprises computing a target deadline for a request.
3. The method according to claim 2, further comprising forwarding any request having a past due target deadline to the queue.
4. The method according to claim 3, wherein said forwarding any request having a past due target deadline is performed even when a queue depth attained exceeds the target queue depth.
5. The method according to claim 2, further comprising monitoring an arrival time of the request.
6. The method according to claim 5, wherein the workload of the request has a target latency and wherein said computing the target deadline for the request comprises combining the target latency of the workload with the arrival time of the request.
7. The method according to claim 6, further comprising monitoring requests of the workload during a time interval for determining a rate of requests for the workload.
8. The method according to claim 7, further comprising adjusting the target latency based on the request rate.
9. The method according to claim 1, wherein the requests are read and write requests directed to a storage device and wherein the queue comprises a device queue included in the storage device.
10. The method according to claim 9, further comprising assigning the requests of each workload to a corresponding input queue prior to said forwarding to the device queue.
11. The method according to claim 9, wherein the device queue has an attained queue depth as of result of said selectively forwarding and further comprising increasing the target queue depth value when the attained queue depth is limited by the target queue depth.
12. The method according to claim 11, wherein said increasing the target queue depth increases the target queue depth by a predetermined multiplier.
13. The method according to claim 1, wherein the computed latency statistic is for a workload having a target latency and wherein said adjusting the target queue depth comprises reducing the target queue depth when the target latency for the workload is less than the computed latency statistic.
14. The method according to claim 13, wherein the target queue depth is reduced proportionally based on comparative values of the target latency and the computed latency statistic.
15. The method according to claim 1, wherein the computed latency statistic is for a workload having a target latency and wherein each workload has a target latency and a computed latency statistic and wherein said adjusting the target queue depth value comprises increasing the target queue depth when each target latency is greater than each computed latency statistic.
16. The method according to claim 1, wherein the latency statistic is computed for each of the plurality of workloads.
17. The method according to claim 16, wherein said adjusting is performed to maintain the computed latency for each workload within the allowable latency statistic for the workload.
18. The method according to claim 17, wherein the target latency statistic is specified by a function such that the target latency for each workload changes depending upon changing characteristics of the workload.
19. A quality-of-service method for data storage comprising:
receiving a function that specifies an allowable latency statistic for each of a plurality of workloads, the allowable latency statistic specified by the function for each workload changing depending upon changing characteristics of the workload, each workload including a plurality of requests; and
scheduling and forwarding the requests to a data storage device for substantially maintaining a monitored latency statistic within the allowable latency statistic for each workload, wherein said forwarding is performed for maintaining a target queue depth at the data storage device.
20. The method according to claim 19, wherein said scheduling comprises prioritizing the requests according to a target deadline for each request.
21. The method according to claim 19, further comprising reducing the target queue depth when the allowable latency statistic for the workload is less than the monitored latency statistic.
22. The method according to claim 19, further comprising increasing the target queue depth when each allowable latency statistic is greater than each monitored latency statistic.
23. A quality-of-service apparatus for a storage system comprising:
a plurality of input queues for receiving requests from a plurality of workloads, wherein each workload is assigned to a corresponding one of the input queues and wherein requests in each input queue are prioritized;
a monitor for measuring a performance statistic for requests of each workload;
a scheduler for selectively forwarding the requests from the input queues to a storage device queue, wherein the scheduler selects a highest priority one of the requests for forwarding to the storage device queue according to a target depth of the storage device queue; and
a controller for adjusting the target depth of the storage device queue according to the performance statistic for the requests of each workload.
24. The apparatus according to claim 23, wherein the requests in each queue are prioritized according to a target deadline assigned to each request.
25. The apparatus according to claim 24, wherein the target deadline for each request is determined from a time of arrival of the request and a target latency for the workload of the request.
26. The apparatus according to claim 24, wherein the monitor monitors a rate of requests for each workload for adjusting the target latency for each workload.
27. The apparatus according to claim 23, wherein the performance statistic for requests of each workload comprises a latency statistic.
28. The apparatus according to claim 27, wherein the controller reduces the target depth when the target latency for each workload is less than the latency statistic for any workload.
29. The apparatus according to claim 28, wherein the target depth is reduced proportionally based on comparative values of the target latency and the latency statistic for the workloads.
30. The apparatus according to claim 27, wherein the controller increases the target depth when each target latency for each workload is greater than the corresponding latency statistic.
31. The apparatus according to claim 27, wherein the device queue has an attained queue depth and wherein the controller increases the target queue depth value when the attained queue depth is limited by the target depth.
32. The apparatus according to claim 31, wherein the target depth is increased by a predetermined multiplier.
33. The apparatus according to claim 31, wherein each workload has one or more corresponding data stores and further comprising a capacity planner for assigning the stores to storage locations.
34. The apparatus according to claim 27, wherein the controller adjusts the target depth of the storage device queue according to the following:
E
=
min
k
\u2062
latencyTarget
\u2061
(
W
k
)
L
\u2061
(
W
k
)
Q
new
=
\u2062
E
*
Q
old
if
\u2062
\u2062
E
<
1
,
(
1
+
\u025b
)
\u2062
\u2062
Q
old
else
\u2062
\u2062
if
\u2062
\u2062
Q
max
\u2265
Q
old
,
Q
old
otherwise
.
wherein Qnew is the adjusted target depth for the storage device queue, Qold is a prior target depth for the storage device queue, Qmax is a maximum depth the device queue attained in a prior predetermined period, L(Wk) is the latency statistic for a workload Wk, and \u03b5 is a predetermined multiplier.
35. The apparatus according to claim 23, wherein the performance statistic is a latency statistic computed for each of the plurality of workloads.
36. The apparatus according to claim 35, wherein the controller adjusts the target depth of the storage device queue to maintain the computed latency for each workload within the allowable latency statistic for the workload.
37. The apparatus according to claim 36, wherein the target latency statistic is specified by a function such that the target latency for each workload changes depending upon changing characteristics of the workload.
38. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps including prioritizing a plurality of requests for each of a plurality of storage system workloads, queuing the requests according to said prioritizing for maintaining a target queue depth, and adjusting the target queue depth in response to a latency statistic for the requests of each workload wherein the latency statistic is computed based on a measured difference between an arrival time and a completion time of the requests of each workload.
39. The program storage device according to claim 38, wherein said prioritizing is performed according to a target deadline assigned to each request determined from a time of arrival of the request and a target latency for the workload of the request.
40. The program storage device according to claim 39, wherein said method steps further include adjusting the target latency for each workload according to a rate of requests for each workload.