From Education

Contents 1 SC09 Student Scientific Programming Contest 1.1 Overall Notes 1.2 Submitting Results 1.3 In-flight Updates 1.4 Problem 1 1.5 Problem 2 1.6 Problem 3 1.7 Problem 4 1.8 Problem 5 1.8.1 Overview 1.8.2 Technology 1.8.3 Description 1.8.4 Grading 1.9 Problem 6

SC09 Student Scientific Programming Contest

Overall Notes

• The contest starts at 9am EDT on Monday November 16th, teams should turn in their results by 5pm EDT on Monday.
• Teams should work in the Education Program booth. Teams are free to leave this space as necessary for bio breaks, to eat, etc.
• Coaches cannot help the teams once the problem descriptions have been released.
• Teams should use the credentials already provided to them for BobSCEd and Puma.
• On BobSCEd you can run jobs interactively or through the scheduler. We have provided hostfiles for use with interactive MPI runs which list the stable nodes, one for the GigE interfaces and one for the Infiniband interfaces. For qsub submissions use the default queue.
• On Puma you can only run jobs through qsub although you can use it interactively as we did during the Introduction to MPI session on Monday. For qsub submissions use the queue named contest.
• Sample PBS submission scripts for Puma and BobSCEd are available.
• If you choose to work on the CUDA problem get in touch with the organizers and we'll arrange for access to those resources.
• If you have questions find one of the organizers by looking in the Education Program booth or by sending email to contest@sc-education.org If there are corrections, clarifications, etc. to the problems during the contest we'll post them on this page under In-flight Updates (see below) and we'll announce that fact in the Education Program booth.

Submitting Results

• Each team will be given a blank USB drive at the beginning of the contest. At 5pm each team will turn-in their USB drive with the following information.

• The root directory of the USB drive must contain exactly one file named README

1. The first line of this file must contain the team name and contact telephone number(s) and email address for the team leader (not the coach). This is the person the organizers will contact if there are questions about the team's results submission.
2. Subsequent lines in the file should contain the name and grade of each member of the team (one line per team member). For grade use the following coding:
   1. For Middle School: MS-5, MS-6, MS-7, MS-8
   2. For High School: HS-9, HS-10, HS-11, HS-12
   3. For Community College: CC-13, CC-14, CC-15, etc
   4. For Four Year: 4Y-13, 4Y-14, etc
   5. For Grad School: GS-1, GS-2, etc
3. The root directory of the USB drive must contain exactly one problem directory for each attempted problem, with the directory name exactly corresponding to the name of the corresponding problem.
4. Each problem directory must contain a file named README, as well as whatever other files and subdirectories the team chooses to convey their solution to the problem.
5. The problem README file must contain a coherent and succinct description of the solution and a description of the contents of the directory for the problem.
6. If you write software as part of a solution to a problem please include the source(s), the binary, and a note about the platform it was built for.

In-flight Updates

1) To access BobSCEd using your ncsi credentials:

• ssh cluster.earlham.edu
• ssh bobsced0

2) To access Puma:

• From cluster.earlham.edu you can ssh chi.kean.edu
• From there you can ssh puma

3) To access the CUDA enabled LittleFe:

• From a machine on the SC commodity network you can ssh commodity-general-267.sc09.org. Use your NCSI username, the password is asdfg

4) Do not use the installed HPL on Puma, download and build your own.

---

Problem 1

Quasicrystals can be modeled as tilings of two dimensional space. The cardinality of the set of possible tilings, ie the size of state-space, is directly related to the entropy of the crystal. Consequently, the problem of counting the number of tilings of 2-D space with a fixed number of shapes of tiles is as important as it is difficult. Solving the problem requires the application of numerical techniques of discrete math in a physics/materials science context.

The full problem description can be found at cluster.earlham.edu:~charliep/SC09-Contest/QUASI

(MH)

Problem 2

General Purpose Graphical Processing Units (GPGPUs) are developing into a powerful and efficient computing platform. They are especially suited for data-processing applications, many of which can be modeled as matrix operations. In some cases, it can be advantageous to perform operations using groups, rings, or fields other than the integers or reals. Solving this problem requires implementing matrix operations over a Galois field on CUDA-enabled GPGPUs.

The full problem description can be found at cluster.earlham.edu:~charliep/SC09-Contest/GFCUDA

(MH)

Problem 3

The simulations are evolving!

Genetic Algorithms are used in function minimization as a method of finding the global minimum for problems with many free parameters and many local minima.

The full problem description can be found at cluster.earlham.edu:~charliep/SC09-Contest/Genetic

(DJ)

Problem 4

Has it cooled down yet?

Simulated Annealing is used in function minimization as a method of finding the global minimum for problems with many free parameters and many local minima.

The full problem description can be found at cluster.earlham.edu:~charliep/SC09-Contest/Annealing

(DJ)

Problem 5

Overview

This problem was inspired by Project Euler Problem 185: Number Mind

Encrypting, and decrypting, messages has been a long standing use of a supercomputer of the day. While not not a state secret cipher, this problem provides a message in a message in a message to uncover. The moral of the story is while there is a well established place for high level highly abstracted languages, algorithmic and performance issues may sometimes dictate other solutions.

This problem challenges you to discover algorithm(s) to simplify and solve a well defined logic puzzle, given that for a contest lasting only a few hours, a brute force algorithm could take days of run-time to complete.

Technology

Required tools

• Programming ability
• Understanding of algorithms, data structures, and complexity analysis

Suggested tools

• Use of MPI (Message Passing Interface) or OpenMP or CUDA (Compute Unified Device Architecture) to use cluster and/or GPU

Description

• Use the available computational resources to code, run and solve the following logic problem:

This problem is like the Project Euler 185 (Number mind) problem, except instead of numbers, lowercase letters are used. The integer following each sequence of 15 letters reflects the number of right characters, in the right position.

This problem could have 0, just 1, or possibly many solutions

whatanswersbein 3
ithecareemplore 3
befreedjustlike 0
howsailoronceto 2
windsaidfreedom 1
vvvvvvvvvvvvvvv 0
naryawordharmed 2
viaourmakingall 2
vvvvvvvvvvvvvvv 0
patternsofgreat 2
worthneedseento 1
beelsefriendnot 0
willtimebetoyou 0
vvvvvvvvvvvvvvv 0
abandonnohopeor 1
startyounotthis 1
taskofmindheart 1
vvvvvvvvvvvvvvv 0
sphinxofblackqu 2
artzjudgemyvowq 1
uickzephyrsblow 0
vexingdaftjimpa 1
ckmyboxwithfive 0
dozenliquorjugs 1
wequicklyseized 0
theblackaxleand 2
justsaveditfrom 1
goingpasthimthe 2
quickbrownfoxju 0
mpsoveralazydog 1

Grading

In a folder named "MessageInMessage" on your team's USB drive:

• Your report of work in an ASCII text file named "ReadMe"
• The source code used to solve the problem

What the graders will be looking for.

• Your report should include a description of the steps taken by the team in working to obtain results. State the problems encountered, the possible solutions considered and tried, and the solution that was implemented and benchmarked.
• Discussion of algorithmic and programming tactics taken to minimize run-time.
• Your report should also include observations on additional steps that might be taken to reduce the overall run-time.

(TM)

Problem 6

Background:

• This problem is centered around the use of HPL, the high-performance Linpack benchmark for distributed memory computers. You will need to download, configure, build and run the benchmark with various specified configurations.

Tasks:

• For this problem use the BobSCEd or Puma cluster. For your timed runs you should use the scheduler so that your processes are the only ones on a given set of nodes during the run (to ensure that you have clean benchmarking data).
• Download HPL (http://www.netlib.org/benchmark/hpl/), configure and build it with the system linear algebra libraries. You may run into dependencies which require you to download and build other packages too.
• Experiment with the problem size definition in HPL.dat until you have a configuration that runs in about 10 minutes with -np 2. Note that changing the number of process may require changes to HPL.dat
• Benchmark your setup using -np 4, -np 8, and -np 12 with your modified HPL.dat configuration file.
• Download the linear algebra library of your choice (e.g. ATLAS or Goto), configure and build it, and then rebuild HPL to use it.
• Benchmark your new setup using -np 4, -np 8, and -np 12 with your modified HPL.dat configuration file.
• Graph the results of your runs showing the performance of the system linear algebra library with the second linear algebra library over the range of parallelism explored. Provide a write-up that describes what you observed about the scalability of HPL and the performance differences between different linear algebra libraries.

(CP)