Changeset 3635


Ignore:
Timestamp:
Mar 8, 2017, 11:16:41 AM (7 weeks ago)
Author:
mulligan
Message:

more work on intro...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • Papers/jar-cerco-2017/introduction.tex

    r3634 r3635  
    2020
    2121A program's non-functional constraints may be given \emph{concretely}, or \emph{asymptotically}.
    22 Asymptotic complexity, as every Computer Science undergraduate knows, is important---but so too is concrete complexity for many applications, including the three we highlighted in our example above.
     22Asymptotic complexity, as every Computer Science undergraduate knows, is important---but so too is concrete complexity for many applications, including the three we highlighted above as examples.
    2323A real-time system's response time is measured in seconds, milliseconds, or some other fundamental unit of time; a cryptographic library must have all execution paths execute in the same number of processor cycles, independent of any input passed by the client; and the size of an embedded controller for a pacemaker is measured in bits, bytes, or some other unit of memory capacity.
     24In all cases, resource consumption is measured in some basal, concrete unit of measure.
    2425
    2526Currently, a program's functional properties can be established by combining user annotations---preconditions, invariants, and so on---with various automated and semi-automated analyses---invariant generators, type systems, abstract interpretations, applications of theorem proving, and so on---on the high-level source code of the program.
     
    2829
    2930By contrast, a program's non-functional properties are established by reasoning on low-level object code produced not by a programmer, but by a compiler.
    30 Whilst analyses operating at this level can and do produce very accurate results, analysis at such a low-level of abstraction invariably has disadvantages:
    31 
    32 \begin{itemize*}
     31Whilst analyses operating at this level can and do produce very accurate results---Worst Case Execution Time (WCET) analysis can be extraordinarily accurate, for example---analysis at such a low-level of abstraction invariably has disadvantages:
     32\begin{itemize}
    3333\item
    3434It can be hard to deduce the high-level structure of the program after compiler optimisations.
     
    4646Performing functional analysis on object code makes it hard for the programmer to provide information about the program and its expected execution, leading to a loss of precision in the resulting analysis.
    4747It is hard for the programmer to understand the results of the analysis, or direct its execution, as high-level abstractions, control flow constructs, and so on, introduced by the programmer are `translated away'.
    48 \end{itemize*}
     48\end{itemize}
     49
     50More ideal would be a combination of high-level reasoning coupled with the accuracy one would expect of WCET, or other static analyses of non-functional properties.
     51This paper presents such a combination.
     52
     53What has previously prevented high-level reasoning about non-functional properties is the lack of a uniform and precise cost model for programs written in programming languages like C.
     54Since modern compilers---as discussed previously---may compile each expression and statement occurrence in radically different ways, optimisations may change control flow, and the cost of an object code instruction may depend on the runtime state of hardware components like pipelines and caches, none of which are visible in the source code, it has not been clear how one could go about defining such a cost model.
    4955
    5056\paragraph{Vision.}
     
    5258information between them and perform both at the same time on high-level source
    5359code.
    54  
    55 What has previously prevented this approach from being applied is the lack of a
    56 uniform and precise cost model for high-level code, since each statement
    57 occurrence is compiled differently, optimisations may change control flow, and
    58 the cost of an object code instruction may depend on the runtime state of
    59 hardware components like pipelines and caches, none of which are visible in the
    60 source code.
     60
    6161
    6262We envision a new generation of compilers that track program structure through
Note: See TracChangeset for help on using the changeset viewer.