Granville Barnett : Algorithms

DSA 0.5 released!

gbarnett — Fri, 30 May 2008 17:09:50 GMT

It's been a while, I've had to work on other stuff for the last 2 or so months which has rendered me with no time. That's the excuses out of the way...

Not much added in this release I would simply point you to the release page for more details.

A friend of mine Luca (translated to english) has joined the project now and will be helping to shape 0.6 and beyond - welcome Luca!!

Download DSA 0.5

DSA Recap

gbarnett — Thu, 08 May 2008 22:42:40 GMT

Some of you will no doubt know that I started a project a while ago now that was intent on bringing implementations of various algorithms and data structures to .NET - but with a different take on things.

Well, after a recent detour with CPUSS (a project that analyses CPU scheduling algorithms - interesting project, give it a download!) in less than a week DSA will receive a lot of time again (next Thursday signals the end of a busy spell of work).

I wanted to thank the few hundred or so who have downloaded DSA 0.4 - you're participation itself is motivation. I have some news for DSA 0.6 that is interesting but I will save that for when DSA 0.5 is released.

I am looking for suggestions of things to add to DSA 1.0 (bare in mind that graphs are on the schedule) so if you can think of a pretty rare data structure or algorithm that you think would be nice to implement then please let me know as I can see whether or not (depending on time constraints) I can get it into DSA 1.0.

The plan is to hopefully release DSA 1.0 by the end of summer (think early September) so I am really expecting things to move quick from a weeks time.

Thank you to all those who have downloaded, there are some exciting things to come!

CPU Scheduling Simulator 1.0 released!

gbarnett — Tue, 08 Apr 2008 21:48:18 GMT

I've said it all before in recent posts, but here it is again - CPUSS is a framework that allows you to design and analyse CPU scheduling algorithms.

Download CPUSS 1.0

There is a tonne of stuff in CPUSS! Most of which is not exposed by the report generation tool (CPUSSRG). Using the CPUSS API you can look at very atomic stats of each and every process that was in the simulation, events for process start, completion, preemption, and resuming.

Download CPUSS 1.0

You can use CPUSS to analyse your won custom algorithms very easily, go to the download page of CPUSS 1.0 and grab the PDF file that explains how to do it, and the API document is quite comprehensive.

Download CPUSS 1.0

If you are interested in scheduling algorithm (strategy) design and analysis then give it a go!

This will be the only release of CPUSS, I may update it a little if there are any major bugs found but it started off as a research project so it won't go any further - it has proved what it needed to prove.

Download CPUSS 1.0

Seriously go check it out if you are into this stuff.

Oh, and finally a BIG thank you to everyone who downloaded the releases and played with them! Thank you!

CPU Scheduling Simulator 0.6 released!

gbarnett — Sat, 22 Mar 2008 20:46:13 GMT

Download CPUSS 0.6

Some cool new features added in this release, they include:

Variance
Standard Deviation
CPU Busy Time
CPU Idle Time
Get average wait time for a category of process (this uses a predicate function)

I am tempted to say that this build is pretty much feature complete, any further additions will be minor.

Future releases will be focused on bug fixes, and a command line tool for invoking load generated process tests etc.

Download CPUSS 0.6

CPU Scheduling Simulator 0.5 released!

gbarnett — Sun, 16 Mar 2008 14:44:30 GMT

Download CPUSS 0.5

I got bored today (I really should be preparing for stuff I have coming up in the next few days!!) looking at random stuff in preparation for the next few days, so I broke off for a while and decided to finish up CPUSS 0.5 release which contains:

Process resumed event
Min/Max wait time achieved by any process during the simulation
WaitTime now computed for every process rather than the total average (which is still there)

Download CPUSS 0.5

CPU Scheduling Simulator 0.4 Released!

gbarnett — Fri, 14 Mar 2008 17:30:47 GMT

Download CPUSS 0.4

A fairly minor release with a little work cleaning the API up a little by reducing ambiguity (definition of ProcessLoad, and Pairs collections).

Also added an event that allows you to subscribe to process preemption, as well as scattered priorities for auto generated process loads.

I added the option to specify a poll time for the priority first and shortest job first strategies, I did debate about just using a standard poll time but I think the flexibility is probably best in this case.

Download CPUSS 0.4

Future iterations

Below are the features that will be added in both CPUSS 0.5 and 0.6 respectively.

CPUSS 0.5

Process resumed event
Wait times for each process
Min wait time
Max wait time

CPUSS 0.6

CPU idle time
CPU busy time
Standard deviation
Average wait time based on a predicate function

CPUSS: Using the SJF Expert Rule

gbarnett — Wed, 12 Mar 2008 19:49:37 GMT

The SJF Expert Rule strategy is designed to elevate the priority of large processes based on a precondition defined by the user, that basically says if the current % of processes in the ready queue is greater than N then execute some of the large processes thus elevating their priorities.

SJF is as you will no doubt no unfair to large processes (that is they require greater CPU burst times). Having large processes always be low down in the stack is really not acceptable in any system, at least if it's not done in a healthy fashion. The reality is that no operating systems use one predefined algorithm, rather they use some dynamic selection policy based on the ready queue and further predictions.

Large Process Elevation

Rather than writing it out again, here is the expert rule definition (all strategies are well documented with advice where required to gain better performance).

By using the expert rule you will be able to swap in large processes for execution based on a threshold defined by you, you will need to analyse the expected number of large processes you estimate at any time t in the ready queue to get the best out of the strategy.

Just like the other strategies it's easy to use and start analysing the data.

    1 using System;
    2 using Cpuss;
    3 using Cpuss.Strategies;
    4 
    5 namespace ConsoleApplication1
    6 {
    7     class Program
    8     {
    9         static void Main()
   10         {
   11             Runner runner = new Runner(12, 4, 34, new ShortestJobFirstExpert(10));
   12             runner.ProcessStarted += (o, e) => Console.WriteLine("PID: {0} Started", e.Id);
   13             runner.ProcessCompleted += (o, e) => Console.WriteLine("PID: {0} Completed", e.Id);
   14             runner.ProcessPreempted += (o, e) => Console.WriteLine("PID: {0} Preempted", e.Id);
   15             runner.Run();
   16         }
   17     }
   18 }

Note: N will be able to be determined by the user as well in the next release (this was an oversight by me in the last release).

Yes, there is a lot more data available! Very simple demo, the code above uses a threshold of 10%.

Preemption support

In change set #9226 and later preemption support is active via events.

Something missing?

I am continuing to add a lot of data spots that can be used for analysis in strategy design and development so if you have any ideas you would like to see let me know!

Download CPUSS!

DSA in review so far

gbarnett — Sun, 09 Mar 2008 21:05:56 GMT

Data Structures and Algorithms (my project on CodePlex) has been an awesome success to date, and continues to grow with every increment and I couldn't be happier about it.

First I must say that for me DSA is really a side side project, so increments tend to be fairly slow (think one month increments - lately I've just been crazy busy though so I'm going to reduce the features per increment to get the bits out quicker so I can keep the healthy feedback loop).

The goal of DSA is simple, provide a comprehensive library of data structures and algorithms that are not in .NET. If you look at the project source you will see that it is extensively tested, it's super important going forward that the bar is kept very high.

This year will see the release of DSA, and I truly believe that it will be one of the most comprehensive implementations of the said features.

Here's to the future of an exciting project - DSA!

CPU Scheduling Simulator (CPUSS) 0.3 released

gbarnett — Wed, 05 Mar 2008 14:22:32 GMT

Download CPUSS 0.3

In this release the new features include:

CPU Activity for each process (so you can perform more in depth analysis)
Average wait time (average processes spent in the ready queue)
Lightweight logger (persists data to a SQL Server database, wraps a LINQ to SQL datacontext)
Expert strategy (view source to find out more)

With CPUSS the idea is that every release really includes a new feature that allows further data gathering which enriches the analysis stage of algorithm design.

The aim is to cover all the main bases in that regard for 1.0.

At the moment the framework is purely used to gather metrics for scheduling strategies, however later on I want to provide some tooling that makes it easier to visualize the results and so on.

Download CPUSS 0.3

If you have any input let me know :-)

Emulating Round Robin with CPUSS

gbarnett — Thu, 28 Feb 2008 14:40:04 GMT

One of the more used strategies in general irrespective of CPU scheduling is the round robin strategy that allows you to define some time quantum that each process will execute for unless within that time it voluntarily releases the CPU, if it doesn't finish within that time quantum then it gets put back into a queue.

Perhaps the hardest part of using the round robin, or certainly the most effective use is gained through appropriate selection of the time quantum. It tends to hold that the best time quantum to use is one that is greater than 80% of all CPU burst times.

Emulating a load scenario using the round robin strategy with CPUSS is dead easy.

    1 using Cpuss;
    2 using Cpuss.Strategies;
    3 
    4 namespace PerfApp
    5 {
    6     class Program
    7     {
    8         static void Main()
    9         {
   10             Runner runner = new Runner(20, 30, 10, new RoundRobin(60));
   11             runner.Run();
   12         }
   13     }
   14 }

Easy. Obviously you will want to perform some analysis on the metrics gathered for each process and so on but I won't go into that here. Also disregard the time quantum I have used (60ns) it was just chosen for demonstration purposes.

Download CPUSS.

DSA 0.4 released!

gbarnett — Thu, 21 Feb 2008 13:33:50 GMT

The latest version of the Data Structures and Algorithms (DSA) library is out!

Download DSA 0.4

This latest release contains the following additions:

QuickSort<T>
UnorderedSet<T>
Heap<T>
ShellSort<T>
InsertionSort<T>
RepeatedWordCount
ToBaseN (Binary, Octal, Hex)

Download DSA 0.4

The documentation has also had a facelift.

DSA 0.5 features will be finalized in the next few days.

Thank you to everyone who has downloaded DSA so far and the feedback provided, so far DSA has been received very well by the community and I hope this latest release will build on that.

For more details on what is in DSA 0.4 please view this page.

Thanks

CPU Scheduling Simulator (CPUSS) 0.2 released!

gbarnett — Fri, 15 Feb 2008 13:23:00 GMT

This release includes a few new scheduling strategies including:

Priority First (PF)
Round Robin (varying time quantum)

Download CPUSS 0.2

As you might expect in CPUSS 0.1 the Process type had no notion of a priority and by default all processes unless stated otherwise have a medium priority.

RR - few words of warning. If you decide to use a time quantum of 1 then you should be aware that you are in effect giving each process in the ready queue 1/n of the CPU where n is the number of processes in the ready queue so it looks like each process has its own CPU, each of which of course is running at 1/n speed of the main CPU. It's somewhat a general rule that the time quantum used should be greater than 80% of CPU bursts (this will reduce the number of context switches).

A custom strategy devised by me was meant to hit this release but I've not had time to properly evaluate the equation I've produced so that will unfortunately have to wait until CPUSS 0.3. The majority of strategies here on in will be those created by me, they may take properties from other established strategies but with various other preconditions and behaviours etc in the hope of creating a "better" strategy for particular scenarios.

There are a few other features I want to add to the actual CPUSS framework in future releases including metrics for preemption, and some events to hook into for that. Quite a few other little features as well would be nice but I'll postpone them to a latter release. Like I mentioned earlier the emphasis for future releases is on the creation of new scheduling strategies using various techniques, e.g. expert rules (this will be in CPUSS 0.3) and fuzzy logic (latter releases).

Download CPUSS 0.2

Creating a quick scheduling simulation using CPUSS

gbarnett — Thu, 31 Jan 2008 09:45:00 GMT

Just a quick note, and most is self explanatory (download CPUSS here). I'll talk about the code after.

using System;
using System.Collections.Generic;
using Cpuss;
using Cpuss.Strategies;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main()
        {
            Runner runner = new Runner(20, 10, 65, new Sjf());
            runner.Completed += (o, e) => Console.WriteLine("Simulation Time: {0}ns Total No. Processes: {1}\n\n", e.TotalTime, e.ProcessCount);
            runner.Run();
            Console.WriteLine("Process Metrics:\n\n");
            foreach (KeyValuePair<int, Process> process in runner.Metrics)
            {
                Process p = process.Value;
                Console.WriteLine("PID: {0} Arrival Time: {1} Start Time: {2} Completion Time: {3}", 
                    p.Id, p.ArrivalTime, p.StartTime, p.CompletionTime);
            }
        }
    }
}

First of all in this case I am creating a simulation using 20 small , 10 medium, 65 large processes (I explained the bounds of the burst time values in this post). The Completed event is pretty self explanatory, this is raised when the simulation has finished executing, i.e. there are no more processes in the ready queue to execute. To start the simulation you need only call the Run method on the Runner instance.

Following the simulation I print out a few of the property values of the metrics gathered throughout the course of the simulation:

Id (synonymous with PID)
Arrival Time
Start Time
Completion Time

I could of included Burst Time as well, but for this demo to make the screen shot look more civilised and less busy (and I understand the console is not the best UI choice to present such data which will be resolved in later releases).

That's it.

Download CPUSS.

CPU Scheduling Simulator (CPUSS) 0.1 released!

gbarnett — Wed, 30 Jan 2008 20:08:00 GMT

I have an interest in CPU scheduling strategies so I thought I would make a framework (CPUSS) by which you could use standard strategies (first-come-first-served, shortest job first, round robin, priority etc) and also create your own and gather metrics from the strategies execution given n processes over T units of time (simulated time, simulated processes).

Download CPUSS 0.1 (or download later after you have read my summary of what is included in this release).

At the moment the features are fairly limited and the framework by which you can plug into to create your own strategies could be better, but remember this is the first early release.

Things to note about this release:

Simulates single core execution (multi-core/processor simulation is something that may be introduced depending on popularity, but would be interesting)
Two strategies ship with the bits at the moment:
- FCFS
- SJF
- More in CPUSS 0.1 this release was primarily built around getting something released pretty quickly and seeing if the simulation environment could hold for various strategies
Metrics are gathered for free when using library strategies
- If you create your own you must register a call to a single method, I won't bore you with the details as the documentation explains everything you need to know
Events exist so you can hook into the simulation, currently:

Runner.Started
Runner.Completed
Runner.ProcessStarted
Runner.ProcessCompleted
A preempted event will get added in the next release

Metrics that are gathered for every process include:

PID
Burst Time
Arrival Time
Start Time
Completion Time
At the moment I've done nothing that requires a process to have a priority but strategies will be introduced in CPUSS 0.2 that will require this.

Auto generation of process "loads" based on the principle that you define processes of varying properties, i.e. small, medium and large processes. The arrival time, and PID of the processes is auto generated. This feature will be particularly useful when testing custom strategies with varying scenarios to gain more balanced and comprehensive data to analyse further.
- Small - 1ms - 40ms
- Medium - 41ms - 100ms
- Large - 101ms - 250ms

I think I have summarized up the main features. Any feedback is gracefully encouraged.

Download CPUSS 0.1

DSA 0.3 released!

gbarnett — Mon, 24 Dec 2007 22:28:00 GMT

Just before Christmas as well :-)

Download DSA 0.3

New features for this release include:

Probability Search
Power algorithm
Greatest common denominator algorithm
Reverse words algorithm
Set collection (will be renamed to OrderedSet in DSA 0.4 and an unordered Set will be introduced in DSA 0.4 as well)
Sequential search
Merge sort
Merge ordered

Some other not so major features include:

Pseudo code for around 75% of everything to enable easy language ports (100% of everything will be in DSA 0.4 - the paper to screen conversion is taking a while)
Queue and Stack have been dropped - DSA will only support collections not in the BCL

ArrayList is being dropped in DSA 0.4

Complete XML documentation for every public algorithm/data structure - also private methods are XML doc'd as well.

Also this is the first release to include offline documentation (or documentation of any kind excluding XML docs).

Download DSA 0.3

DSA 0.4

This release will be out mid February and will introduce some new key algorithms and collections. I am in the process of finalizing the features to be added in DSA 0.4 but you can expect more tree data structures as well as balancing algorithms to further optimise tree data structures. I will post something when this is finalized - will be the back end of December.

Download DSA 0.3

Thank you for your support and if there is anything you would like to suggest then it is not too late...also if you find any issues please let me know.