For Better Performance Please Use Chrome or Firefox Web Browser

VLSI CAD - Spring 2008

VLSI CAD - Spring 2008

Programming Assignment #3: Partitioning

Problem Description

Your task in this programming assignment is to do timing-driven partitioning using the hMetis tool. First do static timing analysis and calculate slacks such that the minimum slack is zero, and then use hMetis to partition the circuit using edge criticality as the weight. The criticality of an edge ei is defined as crit(ei)=1/(1+slack(ei)). Use a 2% balance criteria during partitioning. Run the experiments on ibm01 through ibm05 (these are new circuits that you haven't worked with). Assume that the circuits are combinational. Input pads are nodes with no input and output pads are nodes with no outputs. Note that IBM has randomly pruned out nodes and edges from the circuits so that they are unrecongnizable. As a result, you may see weird nodes with no input/output or other circuit charactersitics that do not make sense.

Since hMetis generates different results in each run, you have to run it 5 times on each of the benchmarks and report the average and the best cut costs. Use a table that shows the cutsize / runtime results.

NOTE: even though you are reporting only the average and min cutsize and runtime in the table, you have to submit all your numbers electronically.

Provided Infrastructure

  • ISPD98 benchmarks: go to the GSRC BookShelf, and follow the link "Bookshelf Slots", and then "Hypergraph Partitioning".  Go to the page that contains the ISPD98 benchmarks.Download ibm01 - ibm05. Use the .net and .are formats.
  • ISPD98 benchmark parser:
    • Suraj Dalvi wrote this parser for the .net and .are formats when he was a student at the U of Minnesota.
    • Note that you DON'T HAVE TO use this parser, or the data structures that Suraj has used. Writing your own code from scratch might be easier than trying to understand how he has written his code. Also, I have stripped the code of some data structure memory allocations, etc. So the code is not complete and not ready to be used with an hMetis call. No guaranties that the code is bug-free. (OK! You got it! I know :)   )
  • hMetis: Follow the link provided in the hMetis paper to get hMetis. Note that the C source code is not provided with hMetis. There is a library module, as well as a number of executables.

Implementation Hints

  • "gettimeofday" is a C function that can be used to measure the hMetis runtime. There are other functions with similar functionalities too.
  • You can either choose to link the hMetis library to your code and do normal C function calls in your program to run hMetis (see hMetis documentation), or you could use the C System("") function call to call the hMetis executable from within your program. Make sure you understand the implications of the two choices.
  • I'd hate to say this, but you really have to read parts of the hMetis manual. Not all of it of course, but at least you have to glance through it.

Submission Process

  1. You have to email ONE zip file called yourName.zip (or yourName.tar.gz) to the TA. Make sure you send the latest version. This file should contain:
    • A README.TXT file that says how to compile your program, what difficulties you had to overcome in this assignment and any useful information you think you should provide for easier grading of your submission.
    • Your compilable source code (do not include the hMetis library or the executables).
    • Any output file(s) that you might have generated, or otherwise any raw data that you have generated.
    • Pdf version of your results table. For each benchmark, run hMetis five times, and only report the results for the best cutsize that hMetis reports.
      • The table should include, for each benchmark, the cutsize (just the number of edges cut with no weights. You should get this number yourself), the weighted cutsize (cutsize as reported by hMetis), the relative size of the larger partitions (e.g., 51.43%) , and runtime in seconds (total runtime of the five runs).
      • Generate another table but this time, do not use timing weights on the edges and do the partitioning using hMetis. Once hMetis is done, report the no-wight cutsize (what hMetis reports), and the weighted cutsize (you should calculate this yourself this time) and the rest of the numbers you reported in the previous table. Also, list the ratio of values compared to Table 1.
      • Below the table, you should list the specifications of the machine you ran the experiments on (CPU, CPU speed, RAM, Operating System)
  2. Bring the hardcopy of your results table (don't forget to write your name) to class too.

Grading

  • Source code submission: 20%
  • Compilation: 10%
  • Bug-free execution: 20%
  • Raw data: 20%
  • Results table and explanations: 30%
  • Program readability and documentation: priceless :)

تحت نظارت وف ایرانی