Back to search

Rochester Institute of Technology

Tree-Based Hardware Recursion for Divide-and-Conquer Algorithms

Abstract

dc:description.abstract

It is well-known that custom hardware accelerators implemented as application-specific integrated circuits (ASICs) or on field-programmable gate arrays (FPGAs) can solve many problems much faster than software running on a central processing unit (CPU). This is because FPGAs and ASICs can have handcrafted data and control paths which exploit parallelism in ways that CPUs cannot. However, designing custom hardware is complicated and implementing algorithms in a way that takes advantage of the desired parallelism can be difficult. One class of algorithms that exemplifies this is divide-and-conquer algorithms. A divide-and-conquer algorithm is a type of recursive algorithm that solves a problem by repeatedly dividing it into smaller sub-problems. These algorithms have a lot of parallelism because they generate a large number of sub-problems that can be computed independently of each other. Unfortunately, traditional stack-based approaches to handling recursion in hardware make exploiting this parallelism difficult. This work proposes a new general-purpose approach to implementing recursive functions in hardware, which we call TreeRecur. TreeRecur uses trees to represent the branching recursive function calls of divide-and-conquer algorithms, which makes it possible to take advantage of their procedure-level parallelism. To allow for design flexibility, TreeRecur executes algorithms using a configurable number of independent function processors. These processors are generated using high-level synthesis, making it easy to implement a variety of different algorithms. Our solution was tested on three different algorithms and compared against software implementations of the same algorithms. Performance results were collected in terms of execution speed and energy consumption. TreeRecur was found to have execution speeds comparable to software when differences in clock speed were accounted for and was found to consume up to 11.2 times less energy.

Degree

thesis:*
Name thesis:degree_name
Computer Engineering (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Engineering (KGCOE)

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Morrison, Braeden
Contributors dc:contributor
  • Marcin Lukowiak

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/10617

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Morrison, Braeden. Tree-Based Hardware Recursion for Divide-and-Conquer Algorithms. Thesis thesis, https://repository.rit.edu/theses/10617