Charles Eric LaForest, PhD Candidate

Why (am I here?)

I want to understand computers from the silicon up to the user interface. I want to make better and beautiful machines, like starships and samurai, not Buicks and bureaucracies. I want to make it possible again for two hairy dropouts named "Steve" to homebrew something insanely great in their garage.

More pragmatically put: I want to be a toolsmith (original link) for scientists in non-computing disciplines.

Whence (do I come from?)

• 1995 - 1999:
  Diploma in Computer Engineering Technology, Algonquin College, Ottawa
• 2004 - 2007:
  Bachelor of Independent Studies, University of Waterloo
  Advisor: Chrysanne DiMarco (UW)
  Thesis Supervisors: Greg Steffan (UoT) and Andrew Morton (UW/Guelph)
  Thesis: Second-Generation Stack Computer Architecture (Waterloo copy)
• 2007 - 2009:
  Master of Applied Science (ECE), University of Toronto
  Advisor: Greg Steffan
  Thesis: Efficient Multi-Ported Memories for FPGAs (T-Space copy)
• 2009 - now:
  Doctor of Philosophy (ECE), University of Toronto
  Topic: FPGA-Centric Coarse-Grain Overlay Architectures
  Advisor: still Greg Steffan

What (interests me)

• Computer Architecture
  • Previously managed the Compiler and Architecture Reading Group.
• Asynchronous Circuits
• Higher-Order Functions (Runtime Code Generation)
• Shared-Nothing Message-Passing Concurrency (à la Erlang)

Where (can you reach me)

• laforest at eecg.utoronto.ca

Writing (I've done over time)

• Efficient Multi-Ported Memories for FPGAs
  Charles Eric LaForest and J. Gregory Steffan
  ACM International Symposium on Field-Programmable Gate Arrays (FPGA), February 2010, Monterey, CA.
  The outcome of my M.A.Sc studies. The paper was very well-received and ranked third in the double-blind review.
  Selected as one of the 25 most significant papers in the first 20 years of the conference: FPGA20 (endorsement)
  Press release from the Dept.: ECE plays major role at FPGA Conference
  
• Multi-Ported Memories for FPGAs via XOR
  Charles Eric LaForest, Ming G. Liu, Emma Rae Rapati, and J. Gregory Steffan
  ACM International Symposium on Field-Programmable Gate Arrays (FPGA), February 2012, Monterey, CA.
  Follow-up on the previous paper. Ranked second in the double-blind review.
• Octavo: An FPGA-Centric Processor Family
  Charles Eric LaForest and J. Gregory Steffan
  ACM International Symposium on Field-Programmable Gate Arrays (FPGA), February 2012, Monterey, CA.
  The current snapshot of my doctoral thesis work.
  
  
• FPGA
  • HDL References
    Because most info online about Verilog and VHDL doesn't get past the baby-steps, here's a collection of solid references.
  • Using Altera's USB-Blaster on Debian Linux
    Most instructions are for Ubuntu, which has a significant difference, so here they are for plain Debian.
• Misc.
  • Substituting fonts in .eps and .fig files
    A couple quick hacks I cooked up to bulk-edit my .fig (and resulting .eps) figure source files to convert them from Times-Roman (for papers) to Helvetica (for slides). Also included a script to bulk-convert them to .jpg if necessary.
  • Chaucer's description of a Grad Student from 600 years ago
    From his Prologue to the Canterbury Tales, circa 1392.
  • Correlation of Ground-Level Computer Installation Error Rates with Solar Activity
    The data suggests that the amount of solar activity does indeed increase the probability of errors in computer systems. Boeing Radiation Effects Laboratory has many papers on this topic. There are more links in Berke Durak's "On the need to use error-correcting memory" and its follow-ups.
  • Canadian Space Gazette (November 2005)
    I wrote "Terrapin Station: An Alternative Approach To Space Exploration" to argue that developing self-sustaining stations should be done sooner than later, and would have great technology transfer potential on Earth. Since then, I've been told that the Van Allen belts pose a bit of a problem...
• Code Structure and Optimization
  • Some Thoughts On Machine Code Organization
    Just a digression on the relationship between iterative, recursive, and threaded machine code, and how the choice of fundamental parameter-passing structure leads to different programming environments.
  • Survey of Loop Transformation Techniques (Slides: PDF PPT)
    A report on all the loop transformation techniques I had to learn in Parallelizing Compilers. If your algorithm is memory-bound, the speedup can be remarkable: "How We Made Our Face Recognizer 25x Faster" In C, in some cases, you'll likely have to use the obscure 'restrict' keyword to give the compiler a chance, else the potential for pointer aliasing makes dependency analysis very hard. Not having array accesses being pointer-based is the main strength of Fortran for such things.
• Parallelism and Message-Passing
  • HashLife on GPU
    A mostly-failed attempt at implementing Gosper's HashLife algorithm on a GPU using CUDA. Hopefully this will help someone else get it right.
  • Message-Passing Concurrency on Shared-Memory Multiprocessors
    Inspired by Erlang, I tested various locking schemes for a message mailbox. Even with thousands of threads contending for a single lock, it turns out that a single, simple Pthread mutex works best due to playing very well with the Linux process scheduler.
• Chaotic Systems and Neural Engineering
  • Finding the Largest Lyapunov Exponent
    In short: use Rosenstein's algorithm over Wolf's. It's much faster and more accurate. (MATLAB code)
  • Second-Order Wiener-Bose Model of a FitzHugh-Nagumo Giant Squid Axon Model
    Finding the number of Laguerre functions is easy enough, but scaling them to the available number of data points is tricky. I initially tried to do it all in MATLAB, but broke down and used LYSIS instead for the modelling. The MATLAB code contains a fast memoized recursive Nth-order Wiener-Bose filter implementation, if you need such a thing.
• Software
  • Batch job queue client and server.
    I wrote this to enable one-at-a-time batch processing of benchmarks for a class, so the students wouldn't pollute each-other's measurements. It did not get used in the end, and I am skeptical about its resilience. At the very least, look at it as an example of Pyro (Python Remote Objects), authentication (and how hard it is to be certain of identity), and faking private class methods in Python.
  • httpfilehits: a per-file web log analyzer, written in Python.
    This takes a raw web server log file and outputs traffic data about each file. Couldn't-find-one-so-I-wrote-one.
• Forth, Stack Machines, and Virtualization
  • A comp.lang.forth thread with much info (and good discussion) about the last bits of stack-machine work I've done. (so far...)
  • Fletcher: Final Project Report
    (Poster, one section per page), (Poster, all one page)
    This was a continuation of my undergraduate work in stack machines: how to extend fast subroutine calls into fast context switching. The end result was a basic kernel and virtual memory model which granted clean and fast machine virtualization. (Don't get too excited. It assumes a very different software universe, where code is routinely dynamically generated.) The Project Design Document and my BIS thesis (see Whence) provide the background details, but are not necessary prior reading.
  • After half a day of writing straight machine code for Gullwing and realizing why people don't do that, I spent a couple days writing a simple symbolic assembler which abuses the C macro system and uses the C compiler's symbol table to do naming and name resolution. You write macros which compile to code which when run generates the actual binary memory image of your assembly code.
    Here's the assembler with the source for the Flight kernel: kergen.c
    And its target hardware parameters: params.h.
    A more detailed description of the Flight kernel source code might help: core_words_v7.txt
    (but it's pretty hard to read by itself. Check my undergrad thesis for useful background.)
  • Extensions To The Flight Programming Language
    (Provides more explanation than in my BIS thesis.) The Flight programming language is based on a small kernel of primitives sufficient to linearly allocate memory, compile stack-based machine code, associate a name to a memory address, look up a memory address from its name, and execute the code there. Although self-contained, this kernel lacks useful features such as the freeing of allocated memory, interactive use of the underlying machine, inline compilation of code and strings, string and number output, flow control constructs, elementary multiplication and division, function composition, lexical closures, and higher-order functions. These features are added to Flight without additions the kernel and without the use of software tools other than Flight itself. The code for these features adds up to about 300 lines of Flight source and compiles into about 2000 words of 32-bit memory.
  • Flight Virtual Machines And Metacompilation
    (This eventually led to the Fletcher project (see above), where I actually implemented the hardware virtualization I speculate about here.) A number of Gullwing virtual machines are written in Flight and their relative overheads are compared. The sources of the overhead are explained in terms of the Popek and Goldberg requirements for machine virtualization, which are then used to derive the necessary changes to the Gullwing architecture to optimally support virtual machines. Some minor alterations are performed on the Flight language kernel to allow for retargeting its compilation. From this is built a framework for expressing the Flight kernel in Flight instead of assembly. When combined with the virtual machines, this allows Flight to create a second, nested instance of itself which cannot affect the first.
  • Communicating Instances Of The Flight Programming Language
    (This is all crude, but might be interesting since FPGAs have the same dual-ported memories I use in this report.) I've altered the Gullwing virtual machine and the Flight language kernel allow for multiple processors to share a common memory. These changes make it possible for an instance of Flight to compile code in memory and have it executed by another processor under software control. This capability is then used to connect via serial channels multiple instances of Flight running on such multiprocessors and use the self-extensible nature of Flight to remotely compile code and make the system appear as a single instance of Flight with parallelism.
• Asynchronous Circuits
  • Burst-Mode Locally-Clocked Asynchronous Circuits
    (My initial foray into asynchronous circuits.) I chose Nowick's Burst-Mode (hazard-free two-level logic) circuits to implement an active and a passive version of an asynchronous four-phase handshake circuit, then used them to build self-timed modules which can generate local clocks with a variable period, exchange data with other asynchronous systems (with early handshake termination if desired), or act as input/output ports with provisions against metastability. I also outline the use of these modules to create an asynchronous implementation of the Gullwing computer architecture.
  • Optimization of Burst-Mode Circuits Using Logical Effort Theory
    (Contains nice nutshell explanations, calculations, and experiments using Logical Effort Theory on control circuits.) The logical effort and parasitic delay of static CMOS logic gates are determined through simple simulation experiments based on Logical Effort theory. This calibrated model is then used to calculate near-optimum gate sizes and path delays for an active/passive pair of Burst-Mode circuits under load. Finally, an extension of Logical Effort theory is applied to the circuits in order to determine their critical delay under an equal gate delay model and compare them to other asynchronous control circuits.

Ways (I took to get here)

• ECE1747 - Parallel Programming
• ECE1755 - Parallel Computer Architecture
• CSC2227 - Topics in the Design and Implementation of Operating Systems
• ECE1754 - Parallelizing Compilers
• ECE540   - Optimizing Compilers
• ECE1764 - Algorithms and Data Structures
• ECE1636 - Supervisory Control of Discrete-Event Systems
• CSC2232 - Topics in System Performance and Reliability
• JEB1444  - Neural Engineering
• ECE1724 - Sp. Topics in Software Eng: Programming Massively Parallel Graphics Processors
• ECE1756 - Reconfigurable Computing and FPGA Architecture (audited)

Work (I've done)

• Curriculum Vitae
• Teaching Assistant:
  • ECE1755 - Parallel Computer Architecture (2008)
  • APS111 - Engineering Strategies and Practice I (2009, 2010)
  • ECE385 - Microprocessor Systems (2010)
  • APS112 - Engineering Strategies and Practice II (2010, 2011)
  • ECE243 - Computer Organization (Head TA) (2011)
  • CSC372 - Microprocessor Software (2011)
  • ECE540 - Optimizing Compilers (2009, 2012)
  • APS105 - Computer Fundamentals (2012)

Winnings (so far)

• 2010 Right Track CAD Graduate Scholarship ($1,500)
• 2011 Queen Elizabeth II/ISS'97: World Telecommunication Congress Graduate Scholarship in Science and Technology ($15,000)
• 2012 Walter C. Sumner Fellowship ($6,000)