# space time estimation - Linux

This is a discussion on space time estimation - Linux ; hi, I have to construct a model to estimate memory space requirements and execution time of a program. I am given the following inputs Program source code in C Underlying target (pentium 4 2.5 Ghz) Operating System ( linux 2.6) ...

# Thread: space time estimation

1. ## space time estimation

hi,

I have to construct a model to estimate memory space requirements and
execution time of a program. I am given the following inputs

Program source code in C
Underlying target (pentium 4 2.5 Ghz)
Operating System ( linux 2.6)
Memory modules (SD RAM)
L1 and L2 caches
gcc compiler

I have a set of simulation programs. I really cannot think of a method
to determine the function which maps the given inputs to the system
size and execution time. Can any one give a pointer to it.

Thanks,

shiva

2. ## Re: space time estimation

"shiva" writes:
> I have to construct a model to estimate memory space requirements and
> execution time of a program. I am given the following inputs
>
> Program source code in C
> [...]
>
> I have a set of simulation programs. I really cannot think of a method
> to determine the function which maps the given inputs to the system
> size and execution time. Can any one give a pointer to it.

You will have to do a complexity analysis of the algorithms describen
in this C source code, and then have an estimation of the input data size.

http://en.wikipedia.org/wiki/Algorithmic_complexity

--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay

3. ## Re: space time estimation

hi,

This is a gud intutive way to begin but it will not be able to give me
any relationship between the input code and memory space used. For
instance if the program complexity is o(n3) then all it says is tat it
will tk more time and space then o(n2) program.

shiva

Pascal Bourguignon wrote:
> "shiva" writes:
> > I have to construct a model to estimate memory space requirements and
> > execution time of a program. I am given the following inputs
> >
> > Program source code in C
> > [...]
> >
> > I have a set of simulation programs. I really cannot think of a method
> > to determine the function which maps the given inputs to the system
> > size and execution time. Can any one give a pointer to it.

>
> You will have to do a complexity analysis of the algorithms describen
> in this C source code, and then have an estimation of the input data size.
>
> http://en.wikipedia.org/wiki/Algorithmic_complexity
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
> Until real software engineering is developed, the next best practice
> is to develop with a dynamic system that has extreme late binding in
> all aspects. The first system to really do this in an important way
> is Lisp. -- Alan Kay

4. ## Re: space time estimation

"shiva" wrote:
>
>I have to construct a model to estimate memory space requirements and
>execution time of a program.
>...
>I have a set of simulation programs. I really cannot think of a method
>to determine the function which maps the given inputs to the system
>size and execution time. Can any one give a pointer to it.

Do you understand that this problem is known to be unsolveable in the
general case? Complexity analysis can give you a rough estimate, but you
cannot look at two arbitrary programs, and say "this program runs 3.2 times
longer and uses 2.72 times as much memory as that program."
--
Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

5. ## Re: space time estimation

shiva wrote:
> hi,
>
> I have to construct a model to estimate memory space requirements and
> execution time of a program. I am given the following inputs
>
> Program source code in C
> Underlying target (pentium 4 2.5 Ghz)
> Operating System ( linux 2.6)
> Memory modules (SD RAM)
> L1 and L2 caches
> gcc compiler
>
> I have a set of simulation programs. I really cannot think of a method
> to determine the function which maps the given inputs to the system
> size and execution time.

And neither can the best minds of our or any previous generation.

You've run up against a variation of the "halting problem"
(http://en.wikipedia.org/wiki/Halting_problem) originally postulated by
Alan Turing in 1936. Specifically, you are exploring the subject of
Rice's theorem (http://en.wikipedia.org/wiki/Rice%27s_theorem).

The best you can do is approximate some values, and choose from them a
representative value for the range of operating values that you expect
your program to encounter.

HTH

--
Lew Pitcher

6. ## Re: space time estimation

hello all,

for the wonderful responses. I know it will be clase to NP hard task.
What i am looking at is not algorithmic complexity but things like
effect of caches on total memory used and execution time, selcted
compiler optimizations etc which we all know intutively has a direct
impact of space and time usuage of any program.

I have choosen a matrix package and will do some timing n space
calculation on it, run some architecture simulator on it and see if the
data could point to some kind of a formulae.

thnks,

shiva.

Lew Pitcher wrote:
> shiva wrote:
> > hi,
> >
> > I have to construct a model to estimate memory space requirements and
> > execution time of a program. I am given the following inputs
> >
> > Program source code in C
> > Underlying target (pentium 4 2.5 Ghz)
> > Operating System ( linux 2.6)
> > Memory modules (SD RAM)
> > L1 and L2 caches
> > gcc compiler
> >
> > I have a set of simulation programs. I really cannot think of a method
> > to determine the function which maps the given inputs to the system
> > size and execution time.

>
> And neither can the best minds of our or any previous generation.
>
> You've run up against a variation of the "halting problem"
> (http://en.wikipedia.org/wiki/Halting_problem) originally postulated by
> Alan Turing in 1936. Specifically, you are exploring the subject of
> Rice's theorem (http://en.wikipedia.org/wiki/Rice%27s_theorem).
>
> The best you can do is approximate some values, and choose from them a
> representative value for the range of operating values that you expect
> your program to encounter.
>
> HTH
>
> --
> Lew Pitcher