Float division by constant integer
A binary logic circuit for determining the ratio x/d where x is a variable integer input, the binary logic circuit comprising: a logarithmic tree of modulo units each configured to calculate x[a: b]mod d for respective block positions a and b in x where b>a with the numbering of block positions increasing from the most significant bit of x up to the least significant bit of x, the modulo units being arranged such that a subset of M−1 modulo units of the logarithmic tree provide x[0: m]mod d for all m∈{1, M}, and, on the basis that any given modulo unit introduces a delay of 1: all of the modulo units are arranged in the logarithmic tree within a delay envelope of [log 2 M]; and more than M−2 u of the subset of modulo units are arranged at the maximal delay of [log 2 M], where 2 u is the power of 2 immediately smaller than M.
1. A binary logic circuit for determining the ratio x/d where x is a variable integer input of w bits comprising M>8 blocks of bit width r≥1 bit, and d>2 is a fixed integer, the binary logic circuit comprising:
a logarithmic tree of modulo units each configured to calculate x[a: b]mod d for respective block positions a and b in x where b>a with the numbering of block positions increasing from the most significant bit of x up to the least significant bit of x, the modulo units being arranged such that a subset of M−1 modulo units of the logarithmic tree provide x[0:m]mod d for all m∈{1, M−1}, and, on the basis that any given modulo unit introduces a delay of 1, all of the modulo units are arranged in the logarithmic tree within a delay envelope of [log 2 M]; and
output logic configured to combine the outputs provided by the subset of M−1 modulo units with blocks of the input x so as to yield the ratio x/d;
wherein the total number of modulo units T in the logarithmic tree for a given number of blocks M is in accordance with the following table:
M
T
24
46
25
48
26
51
27
54
28
58
29
61
30
65
31
69
32
74
33
60
34
62
35
64
36
67
37
69
38
72
39
74
40
78
41
80
42
83
43
85
44
89
45
91
46
94
47
96
48
101
49
103
50
106
51
109
52
113
53
116
54
120
55
123
56
128
57
131
58
135
59
139
60
144
61
148
62
153
63
158
64
164
65
133
66
135
67
137
68
140
69
142
70
145
71
147
72
151
73
153
74
156
75
158
76
162
77
164
78
167
79
169
80
174
81
176
82
179
83
181
84
185
85
187
86
190
87
192
88
197
89
199
90
202
91
206
92
210
93
214
94
217
95
219
96
225
97
227
98
230
99
233
100
237
101
240
102
244
103
247
104
252
105
255
106
259
107
262
108
267
109
270
110
274
111
277
112
283
113
286
114
290
115
294
116
299
117
303
118
308
119
313
120
319
121
323
122
328
123
333
124
339
125
344
126
350
127
356
128
363.
2. A binary logic circuit as claimed in claim 1 , wherein divisor d=2 n +1 for integer n≥2.
3. A binary logic circuit as claimed in claim 1 , wherein the number of blocks of the input is M=2 v +1 for integer v≥3 and at least two modulo units are arranged at the maximal delay of ┌log 2 M┐.
4. A binary logic circuit as claimed in claim 1 , wherein each modulo unit receives a pair of input values, each input value being, depending on the position of the modulo unit in the logarithmic tree, a block of the input x or an output value from another modulo unit, and each modulo unit being configured to combine its pair of input values and perform its mod d calculation on the resulting combined pair of input values.
5. A binary logic circuit as claimed in claim 1 , wherein the modulo units of the logarithmic tree are arranged in a plurality of stages, where no modulo unit of a given stage receives an input value from a modulo unit of a higher stage, the modulo units of a first, lowest stage are each arranged to receive a pair of adjacent blocks from the input x as input values, and the modulo units of each higher S th stage are arranged to receive at least one input from the (S−1) th stage of modulo units.
6. A binary logic circuit as claimed in claim 5 , wherein each modulo unit of the first stage is configured to operate on a pair of input values comprising 2r bits.
7. A binary logic circuit as claimed in claim 5 , wherein each modulo unit is configured to provide an output value of bit width p bits and each modulo unit of a higher stage is configured to operate on:
a pair of input values comprising r+p bits for a modulo unit arranged to receive one of its blocks from the input x; and
a pair of input values comprising 2p bits for a modulo unit arranged to receive output values from other modulo units as its pair of input values.
8. A binary logic circuit as claimed in claim 1 , wherein the number of blocks of the input is
⌈
w
r
⌉
.
9. A binary logic circuit as claimed in claim 8 , wherein
⌈
w
r
⌉
≠
w
r
and one or more of the blocks of the input has a bit width other than r bits or are padded with bits such that all blocks of the input are of bit width r bits.
10. A binary logic circuit as claimed in claim 1 , wherein the bit width of each x[0: m]mod d provided by the logarithmic tree is equal to the minimum bit width p required to express the range of possible outputs of a mod d calculation.
11. A method of synthesising a binary logic circuit for determining the ratio x/d where x is a variable integer input of w bits comprising M>8 blocks of bit width r≥1 bit, and d>2 is a fixed integer, the binary logic circuit comprising a logarithmic tree of modulo units each configured to calculate x[a: b]mod d for respective block positions a and b in x where b>a with the numbering of block positions increases from the most significant bit of x up to the least significant bit of x, the method comprising:
defining an arrangement of modulo units such that:
a subset of M−1 modulo units of the logarithmic tree provide x[0: m]mod d for all m∈{1, M−1}; and
on the basis that any given modulo unit introduces a delay of 1, all of the modulo units are arranged in the logarithmic tree within a delay envelope of [log 2 M]; and
defining output logic configured to combine the outputs provided by the subset of M−1 modulo units with blocks of the input x so as to yield the ratio x/d;
wherein the total number of modulo units T in the logarithmic tree for a given number of blocks M is in accordance with the following table:
M
T
24
46
25
48
26
51
27
54
28
58
29
61
30
65
31
69
32
74
33
60
34
62
35
64
36
67
37
69
38
72
39
74
40
78
41
80
42
83
43
85
44
89
45
91
46
94
47
96
48
101
49
103
50
106
51
109
52
113
53
116
54
120
55
123
56
128
57
131
58
135
59
139
60
144
61
148
62
153
63
158
64
164
65
133
66
135
67
137
68
140
69
142
70
145
71
147
72
151
73
153
74
156
75
158
76
162
77
164
78
167
79
169
80
174
81
176
82
179
83
181
84
185
85
187
86
190
87
192
88
197
89
199
90
202
91
206
92
210
93
214
94
217
95
219
96
225
97
227
98
230
99
233
100
237
101
240
102
244
103
247
104
252
105
255
106
259
107
262
108
267
109
270
110
274
111
277
112
283
113
286
114
290
115
294
116
299
117
303
118
308
119
313
120
319
121
323
122
328
123
333
124
339
125
344
126
350
127
356
128
363.
12. A method as claimed in claim 11 , wherein divisor d=2 n +1 for integer n≥2.
13. A method as claimed in claim 11 , further comprising arranging the modulo units of the logarithmic tree such that more than M−2 u of the subset of M−1 modulo units are arranged at the maximal delay of [log 2 M], where 2 u is the power of 2 immediately smaller than M.
14. A method as claimed in claim 11 , wherein each modulo unit is defined so as to receive a pair of input values, each input value being, depending on the position of the modulo unit in the logarithmic tree, a block of the input x or an output value from another modulo unit, and each modulo unit being configured to combine its pair of input values and perform its mod d calculation on the resulting combined pair of input values.
15. A method as claimed in claim 11 , wherein the modulo units of the logarithmic tree are arranged in a plurality of stages, where no modulo unit of a given stage receives an input value from a modulo unit of a higher stage, the modulo units of a first, lowest stage are each arranged to receive a pair of adjacent blocks from the input x as input values, and the modulo units of each higher S th stage are arranged to receive at least one input from the (S−1) th stage of modulo units.
16. A method as claimed in claim 15 , wherein each modulo unit of the first stage is configured to operate on a pair of input values comprising 2r bits.
17. A method as claimed in claim 16 , wherein each modulo unit is configured to provide an output value of bit width p bits and each modulo unit of a higher stage is configured to operate on:
a pair of input values comprising r+p bits for a modulo unit arranged to receive one of its blocks from input x; and
a pair of input values comprising 2p bits for a modulo unit arranged to receive output values from other modulo units as its pair of input values.
18. A method as claimed in claim 11 , wherein the bit width of each x[0:m]mod d provided by the logarithmic tree is equal to the minimum bit width p required to express the range of possible outputs of a mod d calculation.
19. A method of manufacturing, using an integrated circuit manufacturing system, a binary logic circuit as set forth in claim 1 , the method comprising:
receiving an integrated circuit definition dataset defining a binary logic circuit;
processing the integrated circuit definition dataset to determine a circuit layout; and
generating an integrated circuit according to the integrated circuit definition dataset.
20. A non-transitory computer readable storage medium having stored thereon a computer readable dataset description of a binary logic circuit which, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture an integrated circuit embodying the binary logic circuit, the binary logic circuit being for:
determining the ratio x/d where x is a variable integer input of w bits comprising M>8 blocks of bit width r≥1 bit, and d>2 is a fixed integer, the binary logic circuit comprising:
a logarithmic tree of modulo units each configured to calculate x[a: b]mod d for respective block positions a and b in x where b>a with the numbering of block positions increasing from the most significant bit of x up to the least significant bit of x, the modulo units being arranged such that a subset of M−1 modulo units of the logarithmic tree provide x[0: m]mod d for all m∈{1, M−1}, and, on the basis that any given modulo unit introduces a delay of 1, all of the modulo units are arranged in the logarithmic tree within a delay envelope of [log 2 M]; and
output logic configured to combine the outputs provided by the subset of M−1 modulo units with blocks of the input x so as to yield the ratio x/d;
wherein the total number of modulo units T in the logarithmic tree for a given number of blocks M is in accordance with the following table:
M
T
24
46
25
48
26
51
27
54
28
58
29
61
30
65
31
69
32
74
33
60
34
62
35
64
36
67
37
69
38
72
39
74
40
78
41
80
42
83
43
85
44
89
45
91
46
94
47
96
48
101
49
103
50
106
51
109
52
113
53
116
54
120
55
123
56
128
57
131
58
135
59
139
60
144
61
148
62
153
63
158
64
164
65
133
66
135
67
137
68
140
69
142
70
145
71
147
72
151
73
153
74
156
75
158
76
162
77
164
78
167
79
169
80
174
81
176
82
179
83
181
84
185
85
187
86
190
87
192
88
197
89
199
90
202
91
206
92
210
93
214
94
217
95
219
96
225
97
227
98
230
99
233
100
237
101
240
102
244
103
247
104
252
105
255
106
259
107
262
108
267
109
270
110
274
111
277
112
283
113
286
114
290
115
294
116
299
117
303
118
308
119
313
120
319
121
323
122
328
123
333
124
339
125
344
126
350
127
356
128
363.