CSE 535
Fall 2003 Acceleration of Algorithms
in Hardware J. W. Lockwood

Assignment Schedule

Note: This page will change throughout the semester
Hit [Refresh] often to ensure the page is current

CS/COE 536: Schedule

Monday Wednesday Friday

Wed. Aug 27

First Day of Class
Course Information sheet distributed (TA)
Assigned Reading:

Sudhakar Yalamanchili, VHDL: Starter's Guide: From Simulation to Synthesis, 2001. Chapters 2, 3, 4, 6, 7, 8, and 12.
RFC 760 (IP packets)
RFC 768 (UDP packets)
Layered Protocol Wrappers

Homework 1 Assigned

Mon. Sep 1

Labor Day (No Class)
Wed. Sep 3 (Lecture)

Homework 1 Due
Homework 1 Solutions discussed (TA)
Assigned Reading (for reference)

Xilinx XCV2000E FPGA Documentation

Homework 2 Assigned

Mon. Sep 8: (Lecture)

First Lab: Meet in Urbauer 115
Lecture 1: Introduction
Assigned Reading

Evolvable Internet Hardware Platforms by John W. Lockwood, NASA/DoD Workshop on Evolvable Hardware (EHW'01), Long Beach, CA, July 12-14, 2001, pp. 271-279.

Wed. Sep 10 (Lab)

Homework 2 Due
Machine Problem 0 Assigned
Assigned Reading

An Extensible, System-On-Programmable-Chip, Content-Aware Internet Firewall, by John W. Lockwood, Christopher Neely, Christopher Zuver, James Moscola, Sarang Dharmapurikar, and David Lim, Field Programmable Logic and Applications (FPL), Lisbon, Portugal, Paper 14B, Sep 1-3, 2003.

Mon. Sep 15: (Lecture)

Lecture 2: Language-based Hardware Design

VHSIC Hardware Description Language (VHDL)
Concurrent and Operations
Native operations
Synchronous Storage Elements
Finite State Machines
State Encoding
Technology Mapping

Wed. Sep 17 (Lecture)

Machine Problem 0 Due
Lecture 3a: Synthesis, Placement, and Routing

Logical elements in lookup tables
Random Access Memory (RAM)
Simulated annealing placement algorithm
Interconnect
Design Flow

Lecture 3b: BlockRAMs and the Statistics Counter

Operation the Network Statistics Module
Time-multiplexing of the incrementing circuit
Mapping counter state into BlockRAM
Timing of the BlockRAM

Homework 3 Assigned
Mon. Sep 22 (Lecture)

Lecture 4: Network Intrusion and String Matching

Network intrusion detection
Network intrusion prevention
Threats, attacks, and vulnerabilities.
Issues with header-based security
Regular expression matching
Combined header & payload scanning

Assigned Reading

Implementation of a Content-Scanning Module for an Internet Firewall by James Moscola, John Lockwood, Ronald P. Loui, Michael Pachos, , Field-Programmable Custom Computing Machines (FCCM), Napa, CA, April 9-11, 2003

Wed. Sep 24 (Lecture)

Homework 3 Due (on-line)
Lecture 5: Bloom Filters

String Matching with Bloom Filters
Programming and Querying a Bloom filter
Counting Bloom filters
Bloom filters on the FPX platform
Hashing with parallel BlockRAMs

Assigned Reading

Network Applications of Bloom Filters by Andrei Broder and Michael Mitzenmacher
Deep Packet Inspection Using Parallel Bloom Filters by Sarang Dharmapurikar, Praveen Krishnamurthy, Todd Sproull, John W. Lockwood, , Symposium on High Performance Interconnects (HotI), Stanford, CA, USA, pp. 44-51, Aug. 20-22, 2003.

Machine Problem 1 Assigned

Mon. Sep 29 (Lecture)

Lecture 6: Hash Functions

Direct access tables
Hash function mapping
Collisions
Linked lists
Overflow areas
Re-hashing
Linear probing
Demo (Java applet)

Wed. Oct 1 (Lecture)

Lecture 6b: Hashing (Continued): Generation Functions

Choosing a hash function
Ideal hash function
Uniform hashing
Matrix generator
Collision frequency analysis
Birthday example

Assigned Reading

A Performance Study of Hashing Functions for Hardware Applications, by M.V. Ramakrishna, E. Fu, E. Bahcekapili, International Conference on Computing Information, 1994.

Mon. Oct 6 (Lab)

Machine Problem 1 Due
(by 4:30pm)
Lecture 7: Discussion of Homework 3
and Machine Problem 1 Solutions

Block diagram of module and components
Major entities, signals, registers
Black box declaration
Logic, MUX, and Flops
Initialization circuit
Simulation view
Synthesis steps
Back end flow example
Hints and suggestions

Wed. Oct 8 (Lecture)

Midterm Exam

Format: Open book, open notes
No Computers allowed
No communication devices allowed
Room: McDonnell 361
[NOT our regular classroom!]

Mon. Oct 13 (Lecture)

Assigned Reading

Internet Worm and Virus Protection in Dynamically Reconfigurable Hardware; by John W. Lockwood, James Moscola, Matthew Kulig, David Reddick, Tim Brooks, Military and Aerospace Programmable Logic Device (MAPLD), Washington DC, 2003, Paper E10, Sep 9-11, 2003.

Return Midterms and review Midterm Solutions
Machine Problem 2 Assigned
Wed. Oct 15 (Lecture)

Lecture 8: Worm and Virus Attacks

History of Worms
Robert Morris, Jr.
Code Red (Ver 1 and 2)
Why Worms Spread
Modeling Worms with SI Epidemic Model
Warhol, Flash, and Surreptitious Worms

Assigned Reading

How to 0wn the Internet in Your Spare Time, by Stuart Staniford, Vern Paxson, Nicholas Weaver; Proceedings of the 11th USENIX Security Symposium (Security '02). [Also in .PDF format]

Attend X-fest this Thursday
(Free tutorials for WashU students)
Fri. Oct 17

Special Seminar: How Many Ways to 0wn the Internet: Towards Viable Worm Defenses

11am - Noon
Cupples II,
Room 217

Meet with Nick Weaver

2pm - 3pm
Eads 207

Mon. Oct 20

Lecture 9: Containment of Internet Worms and Computer viruses with Content Filters

Worm spread in unprotected networks
Mitigation of worm threats
Contained with content filtering
Hardware Generation
Rapid Deployment
Active Virus Block
Containment effectiveness

MP2 Hints and Issues

Use syntax like:
signal_name(0)
to access
std_logic_vector(0 downto 0)
MP2 Note: bram_num signal is defined as 15 bits wide to allow for future expansion. We use only 3 bits.

Wed. Oct 22

Discuss Final Project Topics

Review Project Topic List
Review Design Automation Conference (DAC) Student Design Contest submission Rules
Begin Team assignment

Assigned Reading:

David Moore, Colleen Shannon, Geoffrey M. Voelker, Stefan Savage, Internet Worms: Requirements for Containing Self-Propagating Code, Infocom 2003.

Mon. Oct 27 (Lab/Lecture)

Machine Problem 2 Due
Discuss Ad-ware and SearchAssistant
subversion of Google results page
Discuss grading of final projects

Project Design Plan
Status Reports
Peer Review (Most important)
Final Report

Review Current Final Project List
Wed. Oct 29 (Lecture)

Special Guest Lecture on Cybersecurity
David A. Thomas,
Special Agent in Charge
St. Louis FBI

Room: Bryan 509c
(Not the regular classroom)

Final Project Signup Due
Must have your name listed on
Project List by 6pm

Mon. Nov 3 (Lecture)

Final Project Design Plan Due

Prepare 'Project Design Plan'
using format of CS535 Project
PowerPoint template
Present 'Project Design Plan'
to class (10 minutes per team)
Submit your 'Project Design Plan' (ppt file) to gradebot

Wed. Nov 5 (Lab)

Machine Problem 3 Assigned

Bloom Filter Analyzer

Lab session: Meet with your
team to work on final project

TAs, but not instructor,
will be available in lab

Mon. Nov 10 (Lecture)

Final Project: Status Report 1 Due

Prepare 'Project Status Report 1'
using format of CS535 Status
Report Template
Present Status Report
to class (10 minutes per team)
Submit 'Status Report 1' (doc file) to gradebot

Wed. Nov 12 (Lab)

Discuss Testing for Final Project
Discuss Machine Problem 3
Lab session: Meet with your
team to work on final project

Mon. Nov 17 (Lecture)

Final Project: Status Report 2 Due

Prepare 'Project Status Report 2'

Present Status Report
to class (10 minutes per team)
Submit 'Status Report 2' to gradebot

Wed. Nov 19 (Lab)

Machine Problem 3 Due
Lab session: Meet with your
team to work on final project

Mon. Nov 24 (Lecture)

Final Project: Status Report 3 Due

Prepare 'Project Status Report 3'

Present Status Report
to class (10 minutes per team)
Submit 'Status Report 3' to gradebot

Wed. Nov 26 (Lab)

Lab session: Meet with your
team to work on final project

Thanksgiving Break
(Thursday and Friday)

Mon. Dec 1 (Lecture)

Final Project Presentations

Each team gives 15 minute
presentation and demo to class
Submit your 'Final Project Presentation Slides' (ppt file) to gradebot

Homework 4 Due (Tue)
Wed. Dec 3 (Lab)

Lab session: Meet with your
team to work on final project

Using Build Tutorial

Fri. Dec 5 (Lab)

Final Project Writeup Due

Follow rules of DAC Submission Guide and prepare writeup using format like WU Template
Submit your 'Final Project Writeup' to gradebot

Mon. Dec 8 (Lecture)

In-class demonstrations of Final Projects

VHDL, makefiles, and
Simulation scripts due

Submit source code and scripts as
tarfile to gradebot
(.vhdl, makefile, .dat, bitfile)
Do NOT include temporary files
(edif, ngd, ngo, etc. )
Limit total file size to 2 MBytes

Fri. Dec 12 (no class)

Submit Project to DAC

Create your own login/password
Upload your student design contest paper

Mon. Dec 15 (no class)

FINAL version of writeup due

FINAL version of PowerPoint
Presentation slides due

FINAL version of VHDL, makefiles, and
Simulation scripts due

Submit source code and scripts as
tarfile to gradebot
(.vhdl, makefile, .dat, bitfile)
Do NOT include temporary files
(edif, ngd, ngo, etc. )
Limit total file size to 2 MBytes

Wed. Dec 17 (Lab)

Final Exam = Final Project Demo
3-5pm
Submit Peer Evaluations and Course Evaluations

Copyright 2003
John W. Lockwood
Washington University
Saint Louis, MO

Monday	Wednesday	Friday
	Wed. Aug 27 First Day of Class Course Information sheet distributed (TA) Assigned Reading: Sudhakar Yalamanchili, VHDL: Starter's Guide: From Simulation to Synthesis, 2001. Chapters 2, 3, 4, 6, 7, 8, and 12. RFC 760 (IP packets) RFC 768 (UDP packets) Layered Protocol Wrappers Homework 1 Assigned
Mon. Sep 1 Labor Day (No Class)	Wed. Sep 3 (Lecture) Homework 1 Due Homework 1 Solutions discussed (TA) Assigned Reading (for reference) Xilinx XCV2000E FPGA Documentation Homework 2 Assigned
Mon. Sep 8: (Lecture) First Lab: Meet in Urbauer 115 Lecture 1: Introduction Assigned Reading Evolvable Internet Hardware Platforms by John W. Lockwood, NASA/DoD Workshop on Evolvable Hardware (EHW'01), Long Beach, CA, July 12-14, 2001, pp. 271-279.	Wed. Sep 10 (Lab) Homework 2 Due Machine Problem 0 Assigned Assigned Reading An Extensible, System-On-Programmable-Chip, Content-Aware Internet Firewall, by John W. Lockwood, Christopher Neely, Christopher Zuver, James Moscola, Sarang Dharmapurikar, and David Lim, Field Programmable Logic and Applications (FPL), Lisbon, Portugal, Paper 14B, Sep 1-3, 2003.
Mon. Sep 15: (Lecture) Lecture 2: Language-based Hardware Design VHSIC Hardware Description Language (VHDL) Concurrent and Operations Native operations Synchronous Storage Elements Finite State Machines State Encoding Technology Mapping	Wed. Sep 17 (Lecture) Machine Problem 0 Due Lecture 3a: Synthesis, Placement, and Routing Logical elements in lookup tables Random Access Memory (RAM) Simulated annealing placement algorithm Interconnect Design Flow Lecture 3b: BlockRAMs and the Statistics Counter Operation the Network Statistics Module Time-multiplexing of the incrementing circuit Mapping counter state into BlockRAM Timing of the BlockRAM Homework 3 Assigned
Mon. Sep 22 (Lecture) Lecture 4: Network Intrusion and String Matching Network intrusion detection Network intrusion prevention Threats, attacks, and vulnerabilities. Issues with header-based security Regular expression matching Combined header & payload scanning Assigned Reading Implementation of a Content-Scanning Module for an Internet Firewall by James Moscola, John Lockwood, Ronald P. Loui, Michael Pachos, , Field-Programmable Custom Computing Machines (FCCM), Napa, CA, April 9-11, 2003	Wed. Sep 24 (Lecture) Homework 3 Due (on-line) Lecture 5: Bloom Filters String Matching with Bloom Filters Programming and Querying a Bloom filter Counting Bloom filters Bloom filters on the FPX platform Hashing with parallel BlockRAMs Assigned Reading Network Applications of Bloom Filters by Andrei Broder and Michael Mitzenmacher Deep Packet Inspection Using Parallel Bloom Filters by Sarang Dharmapurikar, Praveen Krishnamurthy, Todd Sproull, John W. Lockwood, , Symposium on High Performance Interconnects (HotI), Stanford, CA, USA, pp. 44-51, Aug. 20-22, 2003. Machine Problem 1 Assigned
Mon. Sep 29 (Lecture) Lecture 6: Hash Functions Direct access tables Hash function mapping Collisions Linked lists Overflow areas Re-hashing Linear probing Demo (Java applet)	Wed. Oct 1 (Lecture) Lecture 6b: Hashing (Continued): Generation Functions Choosing a hash function Ideal hash function Uniform hashing Matrix generator Collision frequency analysis Birthday example Assigned Reading A Performance Study of Hashing Functions for Hardware Applications, by M.V. Ramakrishna, E. Fu, E. Bahcekapili, International Conference on Computing Information, 1994.
Mon. Oct 6 (Lab) Machine Problem 1 Due (by 4:30pm) Lecture 7: Discussion of Homework 3 and Machine Problem 1 Solutions Block diagram of module and components Major entities, signals, registers Black box declaration Logic, MUX, and Flops Initialization circuit Simulation view Synthesis steps Back end flow example Hints and suggestions	Wed. Oct 8 (Lecture) Midterm Exam Format: Open book, open notes No Computers allowed No communication devices allowed Room: McDonnell 361 [NOT our regular classroom!]
Mon. Oct 13 (Lecture) Assigned Reading Internet Worm and Virus Protection in Dynamically Reconfigurable Hardware; by John W. Lockwood, James Moscola, Matthew Kulig, David Reddick, Tim Brooks, Military and Aerospace Programmable Logic Device (MAPLD), Washington DC, 2003, Paper E10, Sep 9-11, 2003. Return Midterms and review Midterm Solutions Machine Problem 2 Assigned	Wed. Oct 15 (Lecture) Lecture 8: Worm and Virus Attacks History of Worms Robert Morris, Jr. Code Red (Ver 1 and 2) Why Worms Spread Modeling Worms with SI Epidemic Model Warhol, Flash, and Surreptitious Worms Assigned Reading How to 0wn the Internet in Your Spare Time, by Stuart Staniford, Vern Paxson, Nicholas Weaver; Proceedings of the 11th USENIX Security Symposium (Security '02). [Also in .PDF format] Attend X-fest this Thursday (Free tutorials for WashU students)	Fri. Oct 17 Special Seminar: How Many Ways to 0wn the Internet: Towards Viable Worm Defenses 11am - Noon Cupples II, Room 217 Meet with Nick Weaver 2pm - 3pm Eads 207
Mon. Oct 20 Lecture 9: Containment of Internet Worms and Computer viruses with Content Filters Worm spread in unprotected networks Mitigation of worm threats Contained with content filtering Hardware Generation Rapid Deployment Active Virus Block Containment effectiveness MP2 Hints and Issues Use syntax like: `signal_name(0)` to access `std_logic_vector(0 downto 0)` MP2 Note: `bram_num` signal is defined as 15 bits wide to allow for future expansion. We use only 3 bits.	Wed. Oct 22 Discuss Final Project Topics Review Project Topic List Review Design Automation Conference (DAC) Student Design Contest submission Rules Begin Team assignment Assigned Reading: David Moore, Colleen Shannon, Geoffrey M. Voelker, Stefan Savage, Internet Worms: Requirements for Containing Self-Propagating Code, Infocom 2003.
Mon. Oct 27 (Lab/Lecture) Machine Problem 2 Due Discuss Ad-ware and SearchAssistant subversion of Google results page Discuss grading of final projects Project Design Plan Status Reports Peer Review (Most important) Final Report Review Current Final Project List	Wed. Oct 29 (Lecture) Special Guest Lecture on Cybersecurity David A. Thomas, Special Agent in Charge St. Louis FBI Room: Bryan 509c (Not the regular classroom) Final Project Signup Due Must have your name listed on Project List by 6pm
Mon. Nov 3 (Lecture) Final Project Design Plan Due Prepare 'Project Design Plan' using format of CS535 Project PowerPoint template Present 'Project Design Plan' to class (10 minutes per team) Submit your 'Project Design Plan' (ppt file) to gradebot	Wed. Nov 5 (Lab) Machine Problem 3 Assigned Bloom Filter Analyzer Lab session: Meet with your team to work on final project TAs, but not instructor, will be available in lab
Mon. Nov 10 (Lecture) Final Project: Status Report 1 Due Prepare 'Project Status Report 1' using format of CS535 Status Report Template Present Status Report to class (10 minutes per team) Submit 'Status Report 1' (doc file) to gradebot	Wed. Nov 12 (Lab) Discuss Testing for Final Project Discuss Machine Problem 3 Lab session: Meet with your team to work on final project
Mon. Nov 17 (Lecture) Final Project: Status Report 2 Due Prepare 'Project Status Report 2' Present Status Report to class (10 minutes per team) Submit 'Status Report 2' to gradebot	Wed. Nov 19 (Lab) Machine Problem 3 Due Lab session: Meet with your team to work on final project
Mon. Nov 24 (Lecture) Final Project: Status Report 3 Due Prepare 'Project Status Report 3' Present Status Report to class (10 minutes per team) Submit 'Status Report 3' to gradebot	Wed. Nov 26 (Lab) Lab session: Meet with your team to work on final project Thanksgiving Break (Thursday and Friday)
Mon. Dec 1 (Lecture) Final Project Presentations Each team gives 15 minute presentation and demo to class Submit your 'Final Project Presentation Slides' (ppt file) to gradebot Homework 4 Due (Tue)	Wed. Dec 3 (Lab) Lab session: Meet with your team to work on final project Using Build Tutorial	Fri. Dec 5 (Lab) Final Project Writeup Due Follow rules of DAC Submission Guide and prepare writeup using format like WU Template Submit your 'Final Project Writeup' to gradebot
Mon. Dec 8 (Lecture) In-class demonstrations of Final Projects VHDL, makefiles, and Simulation scripts due Submit source code and scripts as tarfile to gradebot (.vhdl, makefile, .dat, bitfile) Do NOT include temporary files (edif, ngd, ngo, etc. ) Limit total file size to 2 MBytes	Fri. Dec 12 (no class) Submit Project to DAC Create your own login/password Upload your student design contest paper
Mon. Dec 15 (no class) FINAL version of writeup due FINAL version of PowerPoint Presentation slides due FINAL version of VHDL, makefiles, and Simulation scripts due Submit source code and scripts as tarfile to gradebot (.vhdl, makefile, .dat, bitfile) Do NOT include temporary files (edif, ngd, ngo, etc. ) Limit total file size to 2 MBytes	Wed. Dec 17 (Lab) Final Exam = Final Project Demo 3-5pm Submit Peer Evaluations and Course Evaluations