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) ...

+ Reply to Thread
Results 1 to 6 of 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



+ Reply to Thread