Theory and Discussion

• Brief theory of addition
  • Importance
  • Breakdown of addition
  • Brief theory of arithmetic operations
    • Arithmetic computation in logarithmic time
    • How many ways can you associate an expression?
    • What is ■?
    • Why is this huge design space relevant at all?
    • Wait, what about the local component??
• Traditional hardware addition
  • Trees calculate one digit of the answer. What calculates the whole thing?
  • Classic structures
  • Serial structure
  • Sklansky structure
  • Kogge-Stone structure
  • Brent-Kung structure
  • Trade-offs (layers, fan-out, tracks)
  • Problems with classic hardware addition
• Revised hardware addition
  • Setup (RUN ME before executing any code in this section)
  • Trees calculate one digit of the answer. What calculates the whole thing?
  • The classic structures
  • Post-classic structures
• Adder-specific optimizations [Sparseness]
  • Setup (RUN ME before executing any code in this section)
  • Doesn’t everything discussed so far apply to any operation, not just binary addition?
  • Integrating the post-processing logic into the tree
  • Regular sparseness
  • Regular sparseness of higher degree
  • Irregular sparseness
  • Nested sparseness
  • Adder-specific?
• Adder-specific optimizations [Factorization]
  • Setup (RUN ME before executing any code in this section)
  • Integrating the pre-processing logic into the tree
  • Ling factorization
  • What is the Ling factorization expressed in terms of trees?
  • Arbitrary combination of Ling and sparseness
  • Adder-specific?
• Sample traversal through the space of binary trees
  • Setup (RUN ME FIRST)
  • Create and visualize trees
• Logical synthesis of general hardware operations
  • Theory
  • The recipe for any operation
  • Binary addition
  • Theory (skip if this is your first read?)
    • Just addition
    • Carry-generation (non-local aspect of addition)
  • Using the recipe
  • Putting it all together
• Possible expansion: addition-based comparator
  • Discussion
  • Using the recipe (unsigned numbers)
  • Putting it all together
  • Analysis (unsigned numbers)
    • Area
    • Delay
• Possible expansion: non addition-based comparator
  • Discussion
  • Using the recipe
  • Putting it all together
  • Analysis (unsigned numbers)
    • Area
    • Delay
    • Delay
• Possible expansion: adding a constant value
  • Discussion
  • Using the recipe
  • Putting it all together