# source:proto/s2k/trunk/demo/strtoll/design_notes@4014

Last change on this file since 4014 was 4014, checked in by ksherdy, 5 years ago

Edit design notes.

File size: 2.8 KB
Line
1
2Input: 85,24578
3
5
6Rotate: 0000008500024578
7
8
91234
10
11(1 * 1000) + (2 * 100) + (3 * 10) + 4 = 100 ((1*10) + 2) + ((3 * 10) + 4)
12
13Conversion to 32 bit signed integers.
14
15Range -(2^31) to 2^(31-1) or â2147483648 to 2147483647.
16
17At most 10 + 1 (sign prefix) ASCII characters are needed to represent a 32 bit signed integer.
18
19* Serial Conversion.
20
21The serial conversion of a string of integers is commonly expressed as follows.
22
23For example,
24
2547483647 = (4*10^7) + (7*10^6) + (4*10^5) + (8*10^4) + (3*10^3) + (6*10^2) + (4*10^1) + (7*10^0)
26
27
28* Parallel Conversion.
29
30Since addition and multiplcation are associative,
31and since b^k = bm0 *...* bmn = b (m0 + ... + mn) for k = m0 + ... + mn
32we can organize the serial conversion of a string of integers
33into ceiling of log base two passes.
34
3547483647 = (4*10^7) + (7*10^6) + (4*10^5) + (8*10^4) + (3*10^3) + (6*10^2) + (4*10^1) + (7*10^0)
36
37= (10^2(10^2(10^2(4*10^1 + 7*10^0)))) + (10^2(10^2(4*10^1 + 8*10^0))) + (10^2(3*10^1 + 6*10^0)) + (4*10^1 + 7*10^0)
38
39= (10^4)(10^2)(4*10^1 + 7*10^0) + (10^4)(4*10^1 + 8*10^0) + (10^2)(3*10^1 + 6*10^0) + (4*10^1 + 7*10^0).
40
41Pass 1
42
43Pass 2
44
45Pass 3
46
47* Parallel Conversion With Length Sorting.
48
49* Express Parallel Conversion With Length Sorting. This eliminates data movement penalties.
50
51Example. This is a nice example because we can draw upon multiple
52techniques in a single example. e.g. Multi-position advance, interpose32.
53
541,23452345,2
5510|23|45|23|45|02
56
57
59How does Interpose32(x,2).
60
62
63With the odd/even technique we can shift forward 4-bits.
64
6501010101010101010101010101010
661,23,2,45,4221,31,3,908,4,34
671    2            3     4
68  23   45      31         34
69                    908
70          4221
71
72Conversion to 64 bit signed integers.
73
74Range -(2^63) to 2^(63-1) or â9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.
75
76At most 19 + 1 (sign prefix) ASCII characters are needed to represent a 64 bit signed integer.
77
78* s2k Language Design Lessons *
79
801. Odd / Even technique
81
82Pablo Prototype                                                                                 s2k Prototype                                                                                                        Block-at-a-time C++ Implementation
83
84odd  = simd_const_4('a', EOF_mask)      -> stream<4> odd = vstream.constant<4>(10) -> BitBlock odd = simd.constant<2>(10)
85even = simd_const_4('5', EOF_mask)      -> stream<4> even = vstream.constant<4>(5) -> BitBlock even = simd.constant<4>(5)
86
87* Requires specification and mapping of s2k library
88
892(a). Length Sorting (a parallel implementation without gather)
90 (b). Iteration to support sequential gather.
91 (c). Parallel gather and positions
92
933. String to Integer Conversion Algorithm
94
95* Casting operations between power of two field widths.
96* Reduction construct.
97* Delimeter character
98
994. 0, 0x, or 0X
100