CSC352 Homework 2 2013

--D. Thiebaut (talk) 17:10, 20 September 2013 (EDT)

---

This assignment is due on Friday 9/27 Saturday 9/28, at 11:59 p.m.

9/24/13: Look at the end of the Homework for an updated version of RectangleCollection1.java

Multithreaded Packing

The idea for this homework is simple. You get a Processing application that is highly serial and that packs rectangles into a rectangular applet, and you make it parallel by adding a thread that generates packed rectangles, i.e. rectangles that are positioned in the area of the applet in such a way that they touch each other but do not overlap, and at the same time minimize the wasted area.

First, Get the Code

Two different versions of the initial code is available to you. One to run in the native Processing IDE, the other to run with Eclipse (which you are highly encourage to use--Eclipse is a bit tough to setup to run with Processing apps, but one you are done, you benefit from the great features of Eclipse).

The two different versions are available below (but only accessible from Smith campus computers. If you are off-campus, please email me).

This section is only visible to computers located at Smith College

If you go with the native Processing app, just download the *IDE.tgz file and unpack it in a Terminal window on your Mac:

  tar xzvf nameOfTheTgzFile

You will get a new directory called PackingHw2. That's your sketch. Open it with the Processing IDE, and run PackingHw2. You should get a blank applet opened in front of you.

If you go with the Eclipse version (good on you!), then download it and unpack it similarly. You can then import it as File System into your workspace. The main application is PackingHw2. Just run it and you should have a blank applet in front of you.

Time to Play!

Once you have the appet opened in front of you, press the ENTER key a few times. You should see some pink rectangles appear on the screen.

If you keep on going, you should see that as you get closer to the right side of the applet the rectangles are getting smaller and smaller. That's because the collection of rectangles being packed is random, and sorted from largest area to smallest area, and the packing algorithm you are given always packs the largest rectangles first.

Time to Read the Code

The only two java programs you need to read carefully are PackingHw2 and Packer. The header of PackingHw2 indicates how to modify the program to make it pack on its own. Try this modification.

Keep on reading and playing with the code until you feel you understand how both files work. You do not need to study the other java files to do this homework assignment, except perhaps Rectangle and RectangleCollection1.

Your Assignment

Your assignment is to do something very similar to what you did in the Producer-Consumer lab.

You need to add a new thread to the main application (create it in a new class, in a new java file called PackThread) that will be given the list of rectangles to pack (sorted or not) by the setup() function, and then will pack the rectangles as fast as it can, and pass them back to draw() in a thread-safe data structure. Draw() will display the rectangles it gets back, as it gets them back, as fast as it can.

Note that the application you are give is very crude and without much sophistication in the way it packs. But it packs! It is possible (and likely) that if you give it 100 rectangles to pack it may not pack them all. That's fine for us for now. We'll assume the packing done when the last rectangle that can fit in the applet is displayed. That's ok if we miss a few.

Questions

Use the header of your new thread class to answer all the questions

Question 1

Implement the thread-safe data structure with a non-blocking list. Depending on what you use, explain whether the program runs, hangs, or crashes. Explain why.

Question 2

If your answer to Question 1 is that the application hangs or crashes, propose a solution that would prevent such behavior to occur. Make sure you try this solution and that it does help.

If your answer to Question 1 is that the application runs fine from the get-go, figure out how to modify the main application or the run() function of the thread to force the program to hang. Some of the modifications available to you are (but are not limited to) frameRate() and sleep(). Be imaginative.

Question 3

Comment out all the statements that refer to the use of the non-blocking list (so that I can see how you were using it), and implement the thread-save data structure with a blocking list. Run and debug your application. Describe the behavior of your application (runs smooth, stops and goes, hangs, etc...)

If you pick a size-limited structure, what range of sizes give good performance? Are there sizes that create problems? How are they related to the number of rectangles to pack?

Question 4

Tune the application as best as you can and measure its throughput in terms of number of rectangles packed per second. All you need to do for this is measure the current time (in ms) when setup() starts and the time when the last rectangle has been packed and displayed, and output the number of rectangles packed per second to the console.

Indicate what you measure for 100, 500, 1000, 2000, 3000, 5000 rectangles. Make sure you also write down the speed of your processor, in GHz.

Question 5 (Optional and extra-credit--1/3 point)

Could we get some improvement by using several threads? How should these threads operate? If so, what would be the steps one should take to implement this new level of parallelism?

Submission

Tar and zip your files into an arichive. I realize some of you may not have done this often, but it is a good skill to have. There's a lot of help available on the Web regarding this subject. Here's one of many: osxdaily.com/2012/04/05/create-tar-gzip/.

Call your archive hw2.tgz

You may want to rsync it to your beowulf account first. Proceed as follows:

  rsync -av hw2.tgz 352a-xx@beowulf.csc.smith.edu

You will be prompted for your 352a-xx password.

Then submit it on beowulf as follows:

  submit hw2 hw2.tgz

You're done!

Addendum

Here's an updated version of RectangleCollection1.java. This version generates the exact number of rectangles wanted by the user. the previous version generated more rectangles to fully pack the rectangular area.

/**
 * RectangleCollection1.java
 * D. Thiebaut
 * A class that holds randomly generated rectangles.
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class RectangleCollection1 {
	ArrayList<Rectangle> rects;
	RedBlackTreeOfList<Integer, Rectangle> sortedRects;
	int mainW;
	int mainH;
	int N;
	int index = 0;
	boolean debug = false;
	
	public RectangleCollection1( int N, int mainW, int mainH ) {
		this.N = N;
		this.mainW = mainW;
		this.mainH = mainH;
		rects = new ArrayList<Rectangle>();
		sortedRects = new RedBlackTreeOfList<Integer, Rectangle>();
	}

	public void reset() {
		index = 0;
	}
	
	public Rectangle getNextRect( ) {
		if ( index < N ) {
			Rectangle r = rects.get( index );
			index += 1;
			return r;
		}
		else 
			return null;
	}
	
	public void initRandom( int noWanted ) {
		N = noWanted;
		int sqrtN = 1 + (int) Math.sqrt( N );
		Random generator = new Random( System.currentTimeMillis() );
		int totalAreaLeftToCover = mainW * mainH;
		int n = 0;
		System.out.println( "Generating random rects..." );
		while ( n<N && totalAreaLeftToCover > 1 ) {
			Rectangle r = Rectangle.randomRect( 1 + 3 * mainW / 2 / sqrtN, 1+ 3 * mainH / 2 / sqrtN ); 												
			if ( r.getArea() == 0 ) continue;
			if ( r.getArea() > totalAreaLeftToCover ) continue;
			rects.add( r );
			sortedRects.put( r.height, r );
			totalAreaLeftToCover -= r.getArea();
			if ( debug ) { 
				System.out.println( "adding random rect: " + r );
				System.out.println( "totalAreaLeftToCover = " + totalAreaLeftToCover );
			}
			n++;
		}
		
		//--- keep on increasing the size of random rectangles until the total area 
		//--- of all the rectangle is within 1 pixel of the right most edge of the area to cover.
		while ( totalAreaLeftToCover > mainH ) {
			Rectangle r = rects.get( generator.nextInt( rects.size() ) );
			if ( generator.nextBoolean() ) {
				r.width += 1;
				totalAreaLeftToCover -= r.height;
			}
			else {
				r.height += 1;
				totalAreaLeftToCover -= r.width;
			}
		}
		
		//--- Sort by decreasing order ---
		N = rects.size();
		Collections.sort( rects );
		Collections.reverse( rects );
		System.out.println( "Done generating " + N + " random rects" );
	}
	
	public void addFront(Rectangle r) {
		rects.add( 0 , r );
	}

	public static void main(String[] args) {
		RectangleCollection1 rects = new RectangleCollection1( 100, 800, 600 );
		rects.initRandom( 100 );
		
	}


}