Generating Prime Implicants - Analysis and Improvements

A python implemenation of the Quine algorithm is provided (PyQMC.py). It includes a profile statement to measure CPU times and number of function calls. A shell script (make_gnuplot.sh) processes the profile results and displays it through gnuplot.

The idea is to see the limitations of the given code and to improve it. The achieved gain has to be demonstrated by comparing the results for different scenarios.

It is not intended that the whole code is reworked or understood in detail. Instead, interface documentation should be sufficient to reuse existing functions and only dig into those parts, where it is really needed.

Objectives

• Hands on training of Linux/Unix
• Use of command line tools
• Concepts of automation
• Limitations and improvements of the Quine algorithm

Software description

General Flow

The functions have been written in Python. Functions exist for creating random on-sets of Boolean functions. These are called by "make_onsets.py" and the on-sets are piped into "*.tt"-files. Each line contains the onset for one function.
"run_qmc.py" reads all onset files and performs QMC. The CPU time is measured by an profiler and again redirected to a textfile. Command line tools filter to data of interest and prepare vizualization. The CPU times for the basic implementation are written to a tabular seperated value file "basic.dat". This can easily be plotted by gnuplot or further processed by other tools.

Tasks

1. Analyse the performance of the given code.
   Display typical runtimes of the QMC algorithm as function of number of variables.
2. Worst Case simulation.
   What is the worst case? Write a function to generate the corresponding truth table.
   Display typical runtimes (from 1.) and the worst case runtimes into the same graph.
3. Improve the qmc-function by sorting and grouping.
   Measure the additional overhead and compare the performance gains.
   Visualize the improvement.
4. Implement the resolution method.
   Visualize the improvement.
5. Implement a prime cover selection method.

Requirements

1. Python
2. Linux (Well, not really. The files can easily be modified to work on other systems.)
3. gnuplot (Not really. Any program for post processing can be used.)

Getting started

1. Save the tar-ball to your working directory.
2. Unpack it with "tar xvf name_of_tar_ball.tar"
   or "tar xvfz name_of_tar_ball.tar.gz"
3. Enter "bash" to change console
4. Enter the directory and set the variable $PYTHONPATH
   export PYTHONPATH=`working directory can be get with "pwd"`
   check through: echo $PYTHONPATH
5. See what files exsist with ls -R
6. Start interactive Python ("python") and import the module PyQMC.py  
   >>>import src.PyQMC as PyQMC
   >>>help(PyQMC)
7. See what functions already exist:
   >>> import src.BooleanOperations as BO
   >>> help(BO)
8. Exit python with ctrl-D
9. Type "make" and follow the instructions. Let the programm run and understand how the different software interacts. After this, start with the tasks.
10. After make onsets, see the changes with ls -R. You can inspect the new files with any text viewer (vi, kwrite, cat, less)
11. Continue as mentioned in tasks ...

Software

• Shell
  • Command interface that allows also some scripting.
  • Pitfalls
    • Different shells have different syntax (bash, ksh, csh).
    • Very picky on correct syntax, especially white spaces.
  • Getting help
    • man commands
  • Some essential commands (use the internet for more):
    • cd - change directory
    • cp - copy file
    • cp -r copy directory
    • ls - show the content of directory (ls -lrt, ls -R)
    • mv - move something
    • mkdir - create a directory
• Makefiles
  • Very useful for large projects or repetitive tasks. Targets (object files) are rebuilt if a dependency (source file) has been modified.
  • Pitfalls
    • Requieres tabs and not whitespaces.
    • Weird syntax.
    • Dependency structure
• Python
  • Scripting language with a lot of side packages
  • Can be run as interactive shell (just type python) or with a file as argument.
  • Pitfalls
    • Only pointers; can be delecate for lists and default arguments.
    • Indentation levels (set your editor to replace tabulars by 4 spaces.
  • Getting help
    • doc.python.org
    • help( something )
  • Functions you might want to use:
    • range(5) yields [0,1,2,3,4]
    • sorted( [1, 3, 2] ) or inplace sort mylist.sort()

Other software

Download

Download this tarball.