Distributed Computing

For those of you who are interested, here's my PhD thesis:
Adaptive Scheduling in Heterogeneous Distributed Computing Systems.

Abstract

The main focus of this research is in the area of adaptive scheduling for heterogeneous
distributed systems. Given an unreliable, non-dedicated set of
processing and communication resources, a scheduler is required to allocate
tasks to processors. No information about the state of the system, which
can vary over time, or the tasks to be processed, is known in advance and
thus must be estimated dynamically. Current schedulers do not adequately
address this dynamism. To address this, a property estimation method is
presented, which utilizes a k-Nearest Neighbours algorithm, a smoothed average
and an analytical benchmark. These estimated properties are then
used by two different scheduling techniques, which make less restrictive assumptions
than the current state-of-the-art methods. A multi-heuristic evolutionary
method utilizes a genetic algorithm and eight simple heuristics to
efficiently allocate tasks to processors. A deterministic method utilizes the
error inherent in estimating the properties of the system and the execution
time of tasks, to allocate tasks to processors. The algorithms have been
implemented on a real-world heterogeneous distributed system with up to
150 processors. A set of real-world problems from the areas of cryptography,
bioinformatics, and biomedical engineering were used as a test set to measure
the effectiveness of the scheduling algorithms. Experiments have shown that
both methods achieve better efficiency than other state-of-the-art heuristic
algorithms. Finally, a low memory distributed reconstruction application for
large digital holograms is presented, which has significantly increased the size
of holograms that can be reconstructed, over the previous state-of-the-art.

Journal Publications

• Lukas Ahrenberg, Andrew J. Page, Bryan M. Hennelly, John B. McDonald, and Thomas J. Naughton, Using commodity graphics hardware for real-time digital hologram view-reconstruction,Journal of Display Technology, vol. 5, no. 1, 2009.



• Andrew J. Page, Thomas M. Keane and Thomas J. Naughton, Scheduling in a dynamic heterogeneous distributed system using estimation error, Journal of Parallel and Distributed Computing, Volume 68, Issue 11, November 2008, 1452-1462. DOI



• Andrew J. Page, Lukas Ahrenberg, Thomas J. Naughton, Low memory distributed reconstruction of large digital holograms, Optics Express 16, 1990-1995 (2008).



• Thomas M. Keane, Andrew J. Page, Thomas J. Naughton, S.A.A. Travers, J.O. McInerney, Building large phylogenetic trees on coarse-grained parallel machines, Algorithmica, Springer, vol. 45, no. 3, pp. 285-300, July 2006.



• Andrew J. Page, Thomas J. Naughton, Framework for task scheduling in heterogeneous distributed computing using genetic algorithms, Artificial Intelligence Review, Volume 24, Numbers 3-4, November 2005, Pages: 415 - 429, Springer.

Peer Reviewed Conference Papers

• Andrew J. Page, Shirley Coyle, Thomas M. Keane, Thomas J. Naughton, Charles Markham and Tomas Ward, Distributed Monte Carlo Simulation of Light Transportation in Tissue, 8th International Workshop on Java for Parallel and Distributed Computing, proceedings of the 20th International Parallel &Distributed Processing Symposium, Rhodes, Greece, April 2006. IEEE Computer Society.



• Thomas M. Keane, Andrew J. Page, James O. McInerney, Thomas J. Naughton, A high-throughput bioinformatics distributed computing platform, Bioinformatics and its Medical Applications Special Track, The 18th IEEE International Symposium on Computer-Based Medical Systems, pp. 377-382, Dublin, Ireland, June 2005.



• Andrew J. Page, Thomas J. Naughton, Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing, 8th International Workshop on Nature Inspired Distributed Computing, proceedings of the 19th International Parallel & Distributed Processing Symposium, pp. 189a.1-189a.8, Denver, Colorado, USA, April 2005. IEEE Computer Society. Bibtex and abstract



• Andrew J. Page, Thomas M. Keane, Thomas J. Naughton,Bioinfomatics on a Heterogeneous Java Distributed System,7th International Workshop on Java for Parallel and Distributed Computing, proceedings of the 19th International Parallel & Distributed Processing Symposium, pp. 184a.1-184a.4, Denver, Colorado, USA, April 2005. IEEE Computer Society.Bibtex and abstract



• Andrew J. Page, Thomas J. Naughton,Framework for task scheduling in heterogeneous distributed computing using genetic algorithms, 15th Artificial Intelligence and Cognitive Science Conference, eds. Lorraine McGinty and Brian Crean, pp. 137-146,September 8th - 10th 2004, Castlebar, Ireland. ISBN 1-902277-89-9.Bibtex and abstract



• Andrew J. Page, Thomas Keane, Thomas J. Naughton,Adaptive Scheduling Across a Distributed Computation Platform,Third International Symposium on Parallel and Distributed Computing, ed. John P. Morrisson, pp. 141-149,July 2004, Cork, Ireland. ISBN 0-7695-2210-6, IEEE Computer Society.Bibtex and abstract



• Andrew Page, Thomas Keane, Richard Allen, Thomas J. Naughton, John Waldron,Multi-tiered distributed computing platform,2nd International Conference on the Principles and Practice of Programming in Java, pp. 191-194,Kilkenny City, Ireland, June 2003. ISBN 0-9544145-1-9. Bibtex and abstract



• Thomas M. Keane, Andrew Page, Thomas J. Naughton, Simon A.A. Travers,James O. McInerney, Grace P. McCormack, "Heterogeneous distributed computing," IFIP Working Group 8.6 Conference on IT Innovation for Adaptability and Competitiveness, Leixlip, Ireland, 30 May - 2 June 2004.

Updated I've created a distributed web crawler which indexs pages for a search engine. There are 4 machines crawling constantly, plus another server to collate it. There are a few different parts to it: SQL server, Active crawler, Passive crawler, Crawler server.

The SQL server stores a list of webpages to be crawled. For security reasons only a few hosts are able to remotely connect to it. Leaving it open to the world would be crazy. Thus I have two types of crawlers.

The active crawler initiates all communication. It remotely connects to the SQL server, requests a url to crawl and crawls it.

Allocating tasks to processors in a dynamic heterogeneous distributed system can be quite difficult. To generate an efficient schedule you need to know what needs to be processed, and what resources you have at your disposal (processing and communication). Since tasks arrive dynamically for processing, you must estimate how long a previously unseen task will take to execution. Also your resources are changing all the time, so the goal posts are constantly moving. I've been working for the past while on generating good estimates for these. Anyway I've gotten good at predicting the error in my estimates, as you can see in the two graphs below. These were generated using a real world distributed system, and scheduling real problems. Unfortunately most researchers in the field of scheduling only ever run simulations, which can very easily be tweaked to show whatever results the researcher wants, because its an unrealistic (clean-room) user-defined setup. The exact details of how I got this will be in a later paper.

Just got an email (below) about a conference on "knowledge communication via conferences", inviting me to submit a paper, or organise an invited session. Problem is the conference is a SPAM conference, accepting papers on everything. A quick google of "Prof.Nagib Callaos" reveals that this is the same guy who accepted a randomly generated paper to another of his conferences ( Prank fools US science conference). Now as much as I like an excuse to go a conference, this is the sort of conference which would damage your reputation if you put it on your CV. So yea, thats why I generally stick to IEEE or ACM conferences. At least you know there is some minimum sort of standard out there.

Using Google I've found that someone citated my work, which is a first. The paper was my very first paper back in 2003 for PPPJ. My first journal paper (as lead author) has also recently been published.

This is a 4th year project I intend to offer for the coming year (pending approval from Tom Naughton of course). Comments welcome.

Supercomputing benchmarks

Difficulty: Hard - lots of coding
Languages: C and Java
Suitable for CSSE or CS

Every 6 months a list of the Top 500 Supercomputers in the world is published. Each supercomputer on the list ran a benchmark called Linpack which produced the number of floating point operations per second (flop/s) rating, and the system with the highest value gets instant international fame. It has been recognised however that this benchmark is flawed because it only considers one aspect of a supercomputer. The solution is the HPC Challenge (High Performance Computing Challenge). It is a set of 7 benchmarks which tests a wide range of properties about a supercomputer.

We wish to incorporate these benchmarks into a Heterogeneous Java Distributed system

developed in Maynooth. So far only 1 of these benchmarks has been implemented in Java, the rest are implemented in C and/or Fortran. You will have to implement these benchmarks in Java. If done well, these benchmarks could be used in systems worldwide to benchmark Java distributed systems, and could also published. ??

An (incomplete) example of this conversion between? c (stream.c) and java (stream.java)? shows that a 90% of the work involved is simply just directly translating/copy&pasting of code, but its the last 10% that requires the most work.

I got thinking about benchmarks today for distributed computing. Linpack on its own is no longer seen as sufficient to benchmark systems (Linpack gives you the number of floating point operations per second, flops). So a number of other tests have been added for benchmarking, which are collectively called the high performance computing challenge (HPC Challenge).

Unfortunately the distributed system I work with only supports Java, and all of the benchmarks (bar Linpack) seem to be written in C and Fortran.

I took a look at one particular benchmark called STREAM. It benchmarks the sustainable memory bandwidth of a system. I converted the code from C to Java, taking some shortcuts, only to find a major hurdle in my way. The benchmark depends on the program having the ability to measure microseconds (10^-6 seconds) but Java only provides accuracy down to the millisecond (10^-3 seconds), which is a real big hurdle. I have found some hacked solutions to the problem, but they use natively compiled code to get better accuracy, which defeats the platform Independence of Java.

So if anyone happens to know how to get increased time accuracy out of Java please let me know. Ultimatley my aim is to impliement as many of these benchmarks in Java as possible to make the distributed system more accurate in its benchmarking.

UPDATE: Java has provided a mechanism for measuring time in Nano seconds in 1.5.

I have just finished testing a distributed application which can test the strength of passwords hashed using SHA-1, but first I'll give you some of the background.

Last year Vishal made a drunken challenge that I couldn't find his password which had been hashed using the MD5 algorithm. He even offered to give me his hashed password. I countered that it would be possible to brute force a password hashed using MD5 with a distributed system.

So I created a simple algorithm for the distributed system and fired off 2000 sample password hash's to 100 computers. Needless to say it worked like a charm. A simple dictionary attack ( run on the server) found about 200 of these passwords in under a second. The rest were found by brute force within a reasonable amount of time. 95% were found within a few hours. Since its a waste of clock cycles I stopped it. Anyway recently Vishal gave me his password hashed using SHA-1, which reminded me to update the algorithm to do SHA-1. Since Vishal intentionally gave me a well formed, hard password, its unlikely that it will be easy to brute force, but most people, including many computer scientists and IT workers, generally choose weak passwords.

The assumptions I made are:
Most people pick easy to remember passwords.
Words from the dictionary or slight variations are easy to remember, so are commonly used.
Most people do not use uppercase letters or special characters such as ?$%^&*.
Most people pick short passwords ( less than say 10 characters) because they are easy to remember and quicker to type.

So using these assumptions my application can brute force most passwords people choose in a reasonable amount of time. The small percentage of well chosen passwords take vastly more time than the other weak passwords.

When you choose a password you should keep a few things in mind. First of all never use anything which is close to a word in the dictionary. Consider a 7 character password, here are the number of possible passwords depending on what characters you use:

Numbers only	10000000
Lowercase characters	8031810176
Lowercase and numbers	78364164096
Upper/lowercase and numbers	3521614606208
Upper/lowercase, numbers, and symbols	80798284478113
All ASCII codes (256)	72057594037927936

If you use even 1 character from a group of characters ( e.g. uppercase, lowercase, numbers, symbols) you make it much harder for someone to brute force your password. On a final note, it was a fun drunken challenge.

Speedup is a metric used in parallel computing to measure the performance of systems and of the efficiency of parallelized problems. It is very simply just the (total processing time* number of processors)/processing time on 1 processor or (p(t)*n)/p(1). Your speedup measure is only really useful if it can be recreated by another person on another system. Thus to have a generalizable speedup result you must use homogeneous processors. It means that someone with 50 1GHz processors should get similar results as someone with 49 2.4GHz processors (easy verification).



If you use heterogeneous resources you run into major problems, firstly do you use the fastest or slowest processor as the time to execute on 1 processor? Using the slowest processor will give you brilliant speedup results (possibly super-linear), and using the fastest will give poor results. Also the only way to verify heterogeneous speedup results is to have the exact same setup, with the exact same processors, added in the exact same order. In fact for a speedup measurement with 20 heterogeneous processors finding the speedup with 1,2,3...,20 processors, there is 2.4x10^18 (20!) possible variations of your speedup results. This makes the speedup metric unsuitable for heterogeneous computing. In fact there is no generalizable heterogeneous benchmark currently available. Dongarra attempted to address this with Linpack (matrix multiplication) for benchmarking the Top 500 supercomputers, but this only considers the number of floating point operations per second (flop/s) a processor can perform rather than a true generalizable benchmark. The high performance computing challenge (HPCC) introduces a number of other benchmarks, like latency, memory bandwidth etc..., which give a better overall idea of a heterogeneous systems performance, but again this is incomplete and complicated, unlike speedup for homogeneous systems.

Now to move on to my next point. Many researchers do not fundamentally understand speedup and its use as a benchmark, continually using speedup as a comparable benchmark for heterogeneous systems, "engineering" their results to paint their system/scheduler/algorithm/etc... in the best possible light. The results they achieve are of course very very difficult to repeat and verify and are not evidence of generalizablity, scalability etc... For example, I have recently read a paper in a Parallel and Distributed Computing Journal which claimed super-linear speedup by using different versions of the Java Virtual Machine in their distributed system. These results are simply not generalizable, comparable, or scalable (i.e. useless).

There are special cases where you appear to achieve "super-linear" speedup due to memory caching in the processor and less delays accessing hard disks with smaller datasets, but these special cases add their own restrictions, most commonly that the parallelized sub-tasks need to be homogeneous. This is reality, but if we take a quick look at theory we will quickly see that these results are not generalizable. A fundamentally a Turing machine cannot emulate another Turing machine and achieve super-linear speedup. A distributed system is essentially using multiple Turing machines to emulate one "virtual" Turing machine. So if someone claims they can achieve super-linear speedup, their results are very specific to a particular problem, setup, architecture, etc... and not generalizable.

I did some work on a distributed brain imaging simulation. To be exact, a Monte Carlo simulation of light propagation through tissue. I haven't gotten around to publishing it yet, so heres a pretty picture, but only if your on a high bandwidth connection ( picture is 6mb, and thus in the extended section of the post). Obviously you cant publish an animated graphic on paper, so theres nothing to loose. It is hoped that by being able to simulate the paths photons take through tissue, more accurate calibration can be performed on medical imaging systems, because nobody likes firing lasers into their brains for no good reason. I think the real brain for the actual system they are building in Engineering is Charles's.

Some people might wonder what I do. Well I am doing research on adaptive scheduling in heterogeneous distributed computing. Specifically I'm looking at using evolutionary techniques (GAs) to schedule ind pendant tasks on to massively distributed resources (web-computing system/ grids), a prime example of which would be Seti@home.

I'm currently integrating a GA scheduler with the distributed system we've developed. Previously I've been simulating scheduling environments for this GA stuff, which has had some good results compared to the most commonly used schedulers and against the current state of the art GA scheduler. This evolutionary scheduler utilizes 8 heuristics, is dynamic, schedules batches of tasks and works extremely fast. It also considers variable system resources such as processor speeds and network overheads. This hasn't been considered before in other GA schedulers for heterogeneous distributed systems. In case your wondering why I'm using GA's and not other evolutionary scheduling techniques, Prof. H. J. Siegel did a very interesting survey of these techniques and GA's came out on top overall. My scheduler at the moment is only really a load-balancer, but the way I've implemented it allows for precedence constraints to be introduced later. Prof. Zomaya (world expert in field) pointed out to me that precedence constraints over multiple batches is a very difficult problem. It does seem like an interesting problem though.

Anyway over the next few weeks I will be testing out my scheduler with real problems (DPRml, DSEARCH, light propagation through tissue, Pollard Rho key tester for ElGamal, MD5 password tester) on real heterogeneous machines. The results look promising. I'm having to estimate a lot of values, such as the size of tasks (Mflop/s from Linpack) and the network bandwidth and latency, but use an exponential smoothing function which does the job none the less. At the moment I'm just working with multiple homogeneous sets of tasks, but will generalize later.

Task scheduling on a heterogeneous system such as a web computing system is very challenging. Apart from being NP-Hard in the general case, it also has to deal with very variable system conditions.

First of all to address the complexity: many people seem to forget that this is an NP-Hard problem, or recognise it is NP-Hard then make so many restrictions that they actually change the complexity to polynomial. For example I recently read a paper which stated that their scheduler works best when the tasks were the same size( homogeneous) and the processors where the same (homogeneous). Now it doesnt take a genious to figure out that a simple round robin scheduler will also work optimally under this very strict set of assumptions. Then there is the case where a person created a heterogeneous framework (every time I see "framework" I always replace the word with B*S in my mind because it usually is!) but ran their experiments on a nearly homogeneous system. When I say nearly, they had 2 types of processors, which were very similar in speed and same architecture. But even with 2 types of processors the complexity still is polynomial ( I think). Consider 2SAT, which is polynomial, and 3SAT which is NP-Complete and I'm sure you can see what the problem is with a 2 homogenous type system vs a 3 type homogeneous system. Needless to say the experiments weren't generalisable.

There are a few basic topics that you would expect to see in a Distributed Systems course ( and some you shouldnt be seeing too much of!). If they are missing, the course just isnt up to scratch. You should a) run a mile and b) get the lecturer fired for being 10 years out of date.

Essential Topics

• Clusters
• Grids
• XML
• Web/Grid services
• Web computing