Static Pattern-based Execution (SRE) in the Fault Tolerant Scheduler
In the FTS, using static patterns is a simple technique, which uses the concept of (m,k) requirements. We execute a pattern such as {1,1,0,1}. When there is a "1" in the pattern, the reliable version is executed, and when there is "0", the unreliable version is executed. In this pattern, three out of four correct instances are executed, which complies to the (m,k)-requirement (3,4). This means that there will always be three correct executions in every four instances.
There are two types of patterns available for the user, i.e. R-patterns and E-patterns [1]. An R-pattern contains all "0"s at the beginning and all "1"s at the end, such as in {0,0,0,1,1,1,1}. In E-patterns, the "1"s and "0"s are distributed evenly. The pattern's sufficient correctness proofs of complying to an (m,k) requirement can be read in [2] and [3]. The FTS executes this predefined pattern. The pattern is read by the FTS from left to right and top to bottom, if we assume that bytes are on top of each other, such as in the figure below. If the FTS is at the last bit of the pattern, it starts reading the first bit in the pattern again.
An example of an SRE pattern:
->
The starting and ending address of the pattern are specified by pattern_start and pattern_end, which are pointers to a uint8_t variable. The current byte-position is stored in curr_pos, whereas the single bit position in a certain byte is stored in bit_pos. If the pattern should end in midst of a byte, the variable max_bitpos can be specified (0 for the first right bit, and 7 for the most left bit); if it is not specified, max_bitpos will be initialized as 7, which means that the first position (from the left) is the last bit to be read.
uint8_t is always the size 1 byte, independent from the platform.
The three parameters
uint8_t* pattern_start;
uint8_t* pattern_end;
uint8_t max_bitpos
can be specified by the the FTS.
The FTS iterates through this pattern with bitwise operations. The current byte's current bit it will be retrieved by bitwise AND. For example, if {10111011} is the current byte, and bitposition is 4, the red "1" tells us to execute a reliable version next. We do the following operation:
10111011
& 00010000
--------------------
00010000
If the resulting string is equal to "0", then an unreliable version will be executed, otherwise, a reliable version is next. Then bitpos is incremented. If current iteration step is in the last byte's last bit, the current byte will be set to the beginning address of the pattern, and bitpos is set to zero.
Sources:
[1] http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-khchen-lctes.pdf
[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.414.2513&rep=rep1&type=pdf
[3] http://ieeexplore.ieee.org/abstract/document/1661621/
------------------
Today's videos is about how the Hubble Space Telescope is pointed.
TODO - Diagram showing computation overhead and "utilization saving" of the techniques -
There are two types of patterns available for the user, i.e. R-patterns and E-patterns [1]. An R-pattern contains all "0"s at the beginning and all "1"s at the end, such as in {0,0,0,1,1,1,1}. In E-patterns, the "1"s and "0"s are distributed evenly. The pattern's sufficient correctness proofs of complying to an (m,k) requirement can be read in [2] and [3]. The FTS executes this predefined pattern. The pattern is read by the FTS from left to right and top to bottom, if we assume that bytes are on top of each other, such as in the figure below. If the FTS is at the last bit of the pattern, it starts reading the first bit in the pattern again.
An example of an SRE pattern:
->
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
The starting and ending address of the pattern are specified by pattern_start and pattern_end, which are pointers to a uint8_t variable. The current byte-position is stored in curr_pos, whereas the single bit position in a certain byte is stored in bit_pos. If the pattern should end in midst of a byte, the variable max_bitpos can be specified (0 for the first right bit, and 7 for the most left bit); if it is not specified, max_bitpos will be initialized as 7, which means that the first position (from the left) is the last bit to be read.
uint8_t is always the size 1 byte, independent from the platform.
The three parameters
uint8_t* pattern_start;
uint8_t* pattern_end;
uint8_t max_bitpos
can be specified by the the FTS.
The FTS iterates through this pattern with bitwise operations. The current byte's current bit it will be retrieved by bitwise AND. For example, if {10111011} is the current byte, and bitposition is 4, the red "1" tells us to execute a reliable version next. We do the following operation:
10111011
& 00010000
--------------------
00010000
If the resulting string is equal to "0", then an unreliable version will be executed, otherwise, a reliable version is next. Then bitpos is incremented. If current iteration step is in the last byte's last bit, the current byte will be set to the beginning address of the pattern, and bitpos is set to zero.
Sources:
[1] http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-khchen-lctes.pdf
[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.414.2513&rep=rep1&type=pdf
[3] http://ieeexplore.ieee.org/abstract/document/1661621/
------------------
Today's videos is about how the Hubble Space Telescope is pointed.
TODO - Diagram showing computation overhead and "utilization saving" of the techniques -
Kommentare
Kommentar veröffentlichen