IntroductionBase CompilationOptimizationResultsIntroductionBase CompilationOptimizationResultsProgramming by Sketching for Bit-StreamingProgramsArmando Solar-Lezama Rodric Rabbah Rastislav Bod´ıkKemal Ebc˘gluPresented by Michael VrableNovember 10, 2005Sketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsBit-Streaming Programs?IPrograms that manipulate data at the bit-levelIOperate on large stream of dataIKey example: cryptographic algorithms (symmetric ciphers)DES Initial PermutationSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsBit-Streaming Programs?IPrograms that manipulate data at the bit-levelIOperate on large stream of dataIKey example: cryptographic algorithms (symmetric ciphers)DES Initial PermutationSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsKey ConcernsICode should be easy to writeI. . . and easy to verifyIImportant to get cipher implementations right!ICode should execute efficientlyIOperate at word level, not bit levelIAkin to vectorization, but not identicalSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsStreamIt: A Domain-Specific Languagebit->bit filter DropThird {work push 2 pop 3 {for (int i = 0; i < 3; ++i) {bit x = peek(i);if (i < 2) push(x);pop();}}}Sketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsCompiling Bit-Streaming Programsout &= 1101101101101101b;out = (out & 1110011111111111b)| ((out & 0001100000000000b) << 1);out = (out & 1111110011111111b)| ((out & 0000001100000000b) << 2);// etc.IFunctional, but tedious to writeINot very efficientSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsOptimizing Bit-Streaming ProgramsNa¨ıveOptimizedSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsRepresenting Bit-Streaming Programs in StreamBitIFiltersIRepresent as affine transformationIf (x) = Mx + vMDropThird=1 0 00 1 0IPipelinesIf1⇒ f2⇒ f3· · ·ISplitjoinsISplit input (duplicate/round-robin)IFeed through multiple filters in parallelIRecombine outputSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsBase Compilation Algorithm(4-bit architecture)Sketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsInstruction DecompositionIShifts:0 0 01 0 00 1 0IMasks:0 0 00 1 00 0 1Instruction Decomposition Example:1 0 0 00 1 0 00 0 0 10 0 0 0=1 0 0 00 1 0 00 0 0 00 0 0 0+0 0 0 00 0 0 00 0 1 00 0 0 00 1 0 00 0 1 00 0 0 10 0 0 0Sketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsProgram SketchingIOptimized code difficult to produceIMay require locally sub-optimal choicesILarge search space for compiler to exploreISolution: Allow user to guide compiler se arch via sketchesICompiler still responsible for correctnessSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsProgram SketchingSketchDecomp[[shift(1:16 by 0 || 1)],[shift(1:16 by 0 || 2)],[shift(1:16 by 0 || 4)]];Sketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsResolving Permutation SketchesIPermutations an important class of bit-level operationsICompiler may resolve sketches by solving series of constraintsIRepresent permutation as vectorhx1, x2, . . . , xNiwhere xiis the number of positions by which bit i movesIRepresent k-stage decomposition as vectorhy11, . . . , y1N, y22, . . . , y2N, . . . yk1, . . . ykNiSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsEstablishing Permutation ConstraintsIshift(b1, . . . , bMby j)ykbi= jIshift(b1, . . . , bMby ?)ykbi= ykbi+1IFinal positions are correctIpos(bi, p)bi+kXj=1yjbi= pIshift(b1, . . . , bMby a || b)ykbi∈ {a, b}IBits cannot collideSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsEstablishing Permutation ConstraintsIshift(b1, . . . , bMby j)ykbi= jIshift(b1, . . . , bMby ?)ykbi= ykbi+1IFinal positions are correctIpos(bi, p)bi+kXj=1yjbi= pIshift(b1, . . . , bMby a || b)ykbi∈ {a, b}IBits cannot collideSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsSolving Permutation ConstraintsIRepresent linear constraints as matrix equationSy = tISolve via Gaussian eliminationy = z +mXi=1αiviIEquivalent to. . .V α = y − zwith α, y as unknownsIα arbitrary, y limite d by non-linear constraintsSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsOther SketchesIPipeline restructuringIPermutation sketches to aid in affine computationsITable conversionsSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsUser ProductivitySketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsCode OptimizationSketching for Bit-Streaming ProgramsIntroductionBase CompilationOptimizationResultsSummaryIStreamIt an effective domain-specific languageIBase StreamBit compiler produces decent codeISketching guides compiler in producing very high-quality codeIOnly reference code need be correctSketching for Bit-Streaming