Tag Archive for 'btp'

Printing The Last 50 Lines Of A File

Having completed the coding of my BTP, I had to test the program. I wrote down a simple C program to do this and generate the outputs in log files in a specified folder. However, I messed it up big time. The actions included creating temporary files, catenating them and then moving them. I did it horribly wrong and ended up with lots of garbage in each log file. Only the last 50 lines of each file were the results, rest garbage.

I needed a way to retain the last 50 lines of each file and discard the rest. This is when I stumbled across the tail command. It does exactly this ! All you have to do call tail -50 <filename> for each of the files. Sweet !

A simple recursive loop, calling the tail command for each file, and yay I am done with my work. Now it is the time to analyse the results.

To Bug Is Human, To Debug Divine

Debugging is a pretty tiring job. More so if you do not exactly know where you have erred. I spent half the day today debugging my code. Hopefully, it does not have any more bugs.

A day earlier I thought I was done with my BTP coding. I tested the code for small inputs, and the results were as expected. Happy with my work, I wrote a script to let it run a few times on inputs generated following the poisson distribution. When I woke up the next day I was shocked to see the results. They were nothing like what I had imagined. The results had deviated highly from what was expected by theory. Damn! A day’s hard work gone waste.

I sat down to remove any bugs. To elp in the debugging process, I had generated 4 log files – log.xml, run.data, plot.data, miss.data. Poring over these log files and simultaneously running the gdb was a strenous work. I had no idea where the errors were being reported. The aberration becomes observable only after my code has executed for some 10,000 times. It was simply impossible to dry run the code for so long and zero-in on the bug.

I tried a smaller random input, hoping to catch the bug. Luckily enough, this data set produced the error. The deviation was not too obvious, but a hard look at the log files, and I could narrow down the error to a few functions in my code. However, to find the bug, I had to eventually dry run the code for this smaller data set. This took another hour.

All’s well that ends well. I have rectified the error. Basically, I was forgetting to reinitialize an important parameter on the occurance of a particular event. With that done I am hoping to get good results when I wake up tomorrow morning. A good night’s rest is what I deserve. *A pat on my back*. :)

BTP Update

Yay !! Finally I have definitely made some progress in my BTP. I have ironed out all the bugs. As I write, a bash script is running my program over and over again with different parameters as input. The loop will execute some 6*3*100 times. And within each program, there is a time counter which counts forward to 30,000 units.

I have left the whole thing to run in development mode, instead of the deployment mode. Printing out details on the screen is slowing down the generation of results though. Perhaps I must go and sleep while the script does its work. I have been awake for more than 24 hrs now, and sleep is very much welcomed.

I do hope to get some pretty good graph. I am making this siulation for a multi-processor system. However, there is this small issue when it comes to division of work between different processors which I need to discuss with Arnab da. Once done, I should be able to wrap up my project in a matter of day or two.

Fingers crossed. I shall put up the result, provided it is what I expect.

A Logger In C

Now I am working on this fair scheduling for my B Tech Project (BTP). Already having written a 1000 lines of code, it is a great pain to debug it. More so if you do not know which function might have caused the error. I needed a logger which could log all the events. The events include entering a function, any important calculation/decision it makes, any return values, so that if my program breaks down I can exactly pinpoint the source of error simply looking at the log file generated.

I have no idea if any inbuilt logging functionality exists for C programs or not. Either way, I did not have much time to google up and learn how to use it. I decided to make my own logger, a simple one, which would serve my purpose. It hardly took me 10 minutes to get over with it.

One of the important functionalities that I wanted my logger to have is indentation. The log should be properly indented, just the same way as we indent the code. When the program control enters a new function, the logging should get indented to right, and when it leaves the function, the logging should get indented by the same amount to the left. So I defined two macros, INDENT and OUTDENT. To make them work, I defined a global variable – logIndent. The logIndent would at any given time contain the amount of space by which the log has to be indented. Obviously, I initialized it with 0. Also defined is a global variable called indentVal which is the amount of spaces with which the indentation should take place. I like the value to be 2. The two macros are

#define INDENT logIndent += indentVal
#define OUTDENT logIndent -= indentVal

int indentVal = 2;
int logIndent = 0;

I defined another macro called SPACES which would print the number of spaces to produce the required indentation.

int tempIndent;
FILE *logFile;
#define SPACES for(tempIndent = 0; tempIndent < logIndent; tempIndent++) fprintf(logFile, " ");

Obviously tempIndent is a globally declared temporary variable and logFile is the file pointer to the file where the log has to be written. I initialize the logFile pointer in the main() part of my program.

And finally coming to the logger, I created a custom printf() statement using the vprintf() command. I call my logger as LogThis(). Its declaration is as follows

void LogThis(const char *format, ...);

It is constructed as follows

void LogThis(const char *format, ...) {
  va_list args;
  va_start(args, format);
  SPACES;
  vfprintf(logFile, format, args);
  va_end(args);
}

That’s it ! To use this logger, I have to do the following in my function :

#include <stdio.h>
#include <stdarg.h>
void TestLogger() {
  int returnVal;
  float retVal;

  LogThis("<TestLogger>\n");
  INDENT;

  /**
   *  Inside the function do whatever you want to
   */

  LogThis("Returns: %d, %f\n", retrunVal, retVal)

  OUTDENT;
  LogThis("</TestLogger>\n");
}

Done ! A well indented log will be produced. This has really helped me debug the code. I do not have to gdb from the last point that worked in my program. Instead, I know which function the program control was in when it threw an error. I need to gdb from that function onwards only, thus reducing the debuging time considerably. Also, in case of errors, I can increase the debugging data for that particular function, thus eliminating the need to use gdb at all.

BTP On Schedule

Anu

Anu

My BTP is taking up shape now. For a while I have been coding and it was just yesterday that I managed to log some sensible output. A lot of work has yet to be done. But that should not take much time, what with the foundaiton laid and tested. A few more night outs and I shall be up wih good results. The theory part is yet to be touched upon though. A proof has to be done and I have to come up with some sort of a mathematical bound on the under allocation of tasks. This is the tricky part.

Apart from the BTP work, tonight I also have to finish up my scribe and mail it to the professor. I have to scribe a lecture of Cryptography. That’s going to be a hard work, and the highlight for the night. I am dreading having to do a night out and then attend two classes tomorrow starting at 0730 hrs. Hope I don’t sleep midway during the class.

Better get working now. :(

And Then The Coding Begins

As I mentioned yesterday, I have finally managed to complete (read: almost complete) the analytical component of my BTP. Now I need to implement the algorithm and get the results.

It has been a great night out. I have already written ~450 lines of code in C. I have tried the modular approach, breaking things into functions. This way, I test each function individually and am sure that they will work when used together.

Also I have added a new feature in my code this time. Learning from my troubles the last time I coded such a complex algorithm, I realised that a log file proves to be handy. It clearly defines the flow of control, the manipulations and the decisions taken within a loop. Everytime I enter a function, I make a note of it in the log file. Whenever I leave the function, it is noted into the log. All that occurs within the function is properly indented. At the present though I have used a rather brute force method for indenting the log file. I print spaces in the log file using the for loop. I need to find a better way.

Below is the log file that I generated running the incomplete algorithm.

  Number of Processors : 1
  Number of Tasks : 4
  Frame Size : 10
  Number of Groups : 1

  Task   1: e =  18 p =  30 wt = 0.60
  Task   2: e =  18 p =  90 wt = 0.20
  Task   3: e =  18 p = 150 wt = 0.12
  Task   4: e =  18 p = 225 wt = 0.08

  Proc   1: cap =  10

      <<>>naf: 0

      <<>>shr: 6

    Task 1, Frame 0, Share 6

      Frame 0 inserted after -1
      Task 1 inserted into bucket 5 first

      <<>>naf: 0

      <<>>shr: 2

    Task 2, Frame 0, Share 2

      Task 2 inserted into bucket 1 first

      <<>>naf: 0

      <<>>shr: 1

    Task 3, Frame 0, Share 1

      Task 3 inserted into bucket 0 first

      <<>>naf: 1

      <<>>shr: 1

    Task 4, Frame 1, Share 1

      Frame 1 inserted after 0
      Task 4 inserted into bucket 0 first

    <<>>leastFrame: 1

Getting Started With My BTP

It’s high time now that I start coding for my BTP so as to arrive at some result by the next month. However, I am yet to resolve all the analytical issues related to my problem. The biggest of my worries being a mathematical bound over the under-allocation that a task could suffer when scheduled using the algorithm I am working on.

Let me start from the beginning. I have taken up as my BTech project the topic of scheduling tasks on multi-processor system. PPC alloted me to Mr. Arnab Sarkar (Arnab da I call him). I have been working with him for the past few months to arrive at an optimised solution to our problem.

The problem that we are tackling is that there exists an algorithm called ER-Fair which schedules tasks proportionately on a multi-processor system. Arnab da in his research improved the time complexity by using frames. He divided the time into frames, of equal sizes and then alloted the tasks to these frames. Inside the frame, ER-Fair scheduling can be used to arrive at fair scheduling. The drawback was that ER-Fair requires a higher time complexity than a simple Round Robin algorithm. So the motivation was to replace the ER-Fair algorithm by an O(1) round robin algorithm without compromising on the fairness.

VTRR is one such algorithm. But then I was not able to derive any mathematical bounds for the maximum under-allocation that a task can suffer when scheduled using the VTRR algorithm, and by definition VTRR does not guarentee against under-allocation. So we could be losing fairness if we used just the VTRR algorithm. One pathological case where this happens is when there are 4 tasks to be scheduled and they have weights of 9, 1, 1, 1. The VTRR algo then schedules Task A, B, C, D and only then returns back to again schedule A. But by this time A has been under-allocated. Now consider a system where there are many more tasks than just 4, this boundary case implies a huge deviation from the required fairness.

We found a way around this by using groups within frames. Tasks are divided into groups on the basis of their shares. This ensures that all tasks of similar weights are put into the same group, therby avoiding the occurance of any case as mentioned above. The weight of the group would be the combined weight of all the tasks. To the external scheduler, a group would appear as a single task which needs to be scheduled. Since we shall be creating fixed number of groups, using ER-Fair algorithm for scheduling the groups should take only O(1) time.

The tasks within a single group can be scheduled using VTRR algorithm. But I met with the smae problem once again, that of deriving the bounds for the under-allocation. This very evening though, Arnab da found another interesting algorithm. It is a slight modification of the VTRR algorithm and performs better in the same complexity range. This one works with ensuring that the error (defined as the amount of work received less what the task should have been serviced) never exceeds 1. If it does, then either the first or the next task is selected on the basis of which task has lesser error. Being a simple round robin algorithm, it is O(1) and easier to implement than the VTRR. Also I have managed to come up with a few equations to bound the under-allocation. I am not getting my hopes high yet, not until Arnab da checks it and finds it right.

Also we met PPC today. It was mostly Arnab da and him discussing the problem and the solution, I was just a third person observer. PPC said the idea is good and told me to come up with some analytical result as to what would be the optimal way of putting the tasks into groups. Also, he said if we code the algorithm and if the observation of under-allocations vs. number of groups comes out as a rectangular hyperbola, dipping quickly as the number of groups increases, then it could be a successful experiment. The reason is that if the number of groups is 1, then the system is equivalent to VTRR which does not haveĀ  bounded under-allocation, and if the number of groups equals the number of tasks, then the system is effectively being scheduled using just the ER-Fair algorithm which is not O(1). So if we can show that the idea of a few groups can schedule the system in O(1), it’ll be successful work.

Back To Work :(

Now with the interviews over, and suffient rest its time to get back to work. I do feel a bit lazy though, wanting to postpone the moment when I would have to deal with those nasty pointers again, but its high time. A few hours of serious coding is all that is needed.

Happy coding.

Too Much To Take

Today I am reaping the benefits of having made reading a good habbit. I have my GRE exam in a couple of days and without any remorse I admit that my preparations have not been upto the mark. But the reason was just that I am no longer motivated enough to write this exam. It has become mere formality, to get a good score. I dont think I would care even if I got a low score.

And it’s good that I have mentally prepared myself to accept low score in GRE, afterall that is what I will get. Inadequate preparation has really dented any chance I had to score well.

However, at the moment my biggest concern is not the GRE. Instead, it is my BTP. I have my viva on the 4th of november, and yet have’t done anything substancial. I did work on a project with determination to arrive at a result, but now have fallen short of time. I need to get some work done this week.

We had a great time in the wing though, bursting crackers and all. Good to spend time with the 3rd years of the wing. Have posted a few photos on picasa. Sooner than later I shall be adding them here too. Tomorrow being the Diwali, we shall definitely do something worthwhile – already there were plans of going out for dinner, but nothing confirmed for sure.

I now need to sleep, must complete Barrons tomorrow, so that I have my wednesday for revision and practising on sample test. I really hope I score 1300, even though the chances appear feeble.




Theme Tweaker by Unreal