wiki:BlockByBlockProcessingOfASequentialLoop

Version 1 (modified by eamiri, 9 years ago) (diff)

--

Block by Block Processing of a Sequential Loop

By a sequential loop we mean a while loop that sequentially processes bit streams within one block. Examples of sequential loops are while loop in start tag parsing and Comment-CDATA-PI parsing. Currently when this loops are modified to process data block by block, we introduce one new variable in addition to carry for each addition inside the loop. Also we introduce a new variable that is logical or of all carries inside the loop. This variable is tested in each iteration as part of loop condition. An example can be found here.

The new strategy for block by block processing removes the need to extra variables and extra condition added to the loop condition. The implementation of this idea in C and Python is different. Here we consider Python implementation and explain differences between the new idea and this example. The basic idea for any block by block processing of a sequential loop is that the first iteration of the loop must consume carries of the previous block. Also if any carry is generated in any iteration of the loop, it must be saved and passed to the next block. In this example both tasks are done within the body of the loop. The new idea is to copy the body of the loop before the loop once and consume carries of the last block in that unrolled iteration. Then within the body of the loop we only need to keep record of newly generated carries. Since carries of the last block are already consumed we don't need any condition on carries in the loop condition. Also carry variables do not save any information now and we can use them to record newly generated carries and so additional variables are not needed.