source: proto/s2k/demo/strtoll/design_notes @ 3609

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

Added needle-in-haystack demo.

File size: 2.7 KB
Line 
11234
2
3(1 * 1000) + (2 * 100) + (3 * 10) + 4 = 100 ((1*10) + 2) + ((3 * 10) + 4)
4
5Conversion to 32 bit signed integers.
6
7Range -(2^31) to 2^(31-1) or −2147483648 to 2147483647.
8
9At most 10 + 1 (sign prefix) ASCII characters are needed to represent a 32 bit signed integer.
10
11* Serial Conversion.
12
13The serial conversion of a string of integers is commonly expressed as follows.
14
15For example,
16
1747483647 = (4*10^7) + (7*10^6) + (4*10^5) + (8*10^4) + (3*10^3) + (6*10^2) + (4*10^1) + (7*10^0)
18
19
20* Parallel Conversion.
21
22Since addition and multiplcation are associative,
23and since b^k = bm0 *...* bmn = b (m0 + ... + mn) for k = m0 + ... + mn
24we can organize the serial conversion of a string of integers
25into ceiling of log base two passes.
26
2747483647 = (4*10^7) + (7*10^6) + (4*10^5) + (8*10^4) + (3*10^3) + (6*10^2) + (4*10^1) + (7*10^0)
28
29= (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)
30
31= (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).
32
33Pass 1
34
35Pass 2
36
37Pass 3
38
39* Parallel Conversion With Length Sorting.
40
41* Express Parallel Conversion With Length Sorting. This eliminates data movement penalties.
42
43Example. This is a nice example because we can draw upon multiple
44techniques in a single example. e.g. Multi-position advance, interpose32.
45
461,23452345,2
4710|23|45|23|45|02
48
49
50How does Advance(x,2) work?
51How does Interpose32(x,2).
52
53Mark even and advance().
54
55With the odd/even technique we can shift forward 4-bits.
56
5701010101010101010101010101010
581,23,2,45,4221,31,3,908,4,34
591    2            3     4
60  23   45      31         34
61                    908
62          4221
63
64Conversion to 64 bit signed integers.
65
66Range -(2^63) to 2^(63-1) or −9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.
67
68At most 19 + 1 (sign prefix) ASCII characters are needed to represent a 64 bit signed integer.
69
70* s2k Language Design Lessons *
71
721. Odd / Even technique
73
74Pablo Prototype                                                                                 s2k Prototype                                                                                                        Block-at-a-time C++ Implementation
75
76odd  = simd_const_4('a', EOF_mask)      -> stream<4> odd = vstream.constant<4>(10) -> BitBlock odd = simd.constant<2>(10)
77even = simd_const_4('5', EOF_mask)      -> stream<4> even = vstream.constant<4>(5) -> BitBlock even = simd.constant<4>(5)
78
79* Requires specification and mapping of s2k library
80
812(a). Length Sorting (a parallel implementation without gather)
82 (b). Iteration to support sequential gather.
83 (c). Parallel gather and positions
84
853. String to Integer Conversion Algorithm
86
87* Casting operations between power of two field widths.
88* Reduction construct.
89* Delimeter character
90
914. 0, 0x, or 0X
92
93* Lookahead
94
955. Write out (a construct for sequential iteration)
96   
97! Need a way to map file positions to register positions.
Note: See TracBrowser for help on using the repository browser.