The Experts below are selected from a list of 45 Experts worldwide ranked by ideXlab platform

Sung-soo Lim - One of the best experts on this subject based on the ideXlab platform.

  • An accurate worst case timing analysis for RISC processors
    1995
    Co-Authors: Sung-soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, Soo-mook Moon, Chong Sang Kim
    Abstract:

    An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real-time systems. In RISC processors, the execution time of a Program Construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, we propose extensions to the original timing schema where the timing information associated with each Program Construct is a simple time-bound. In our approach, associated with each Program Construct is worst case timing abstraction, (WCTA), which contains detailed timing information of every execution path that might be the worst case execution path of the Program Construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time-bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across Program Constructs. This paper also reports on preliminary results of WCET analysis for a RISC processor. Our results show that tight WCET bounds (within a maximum of about 30% overestimation) can be obtained by using the revised timing schema approach.

  • An accurate worst case timing analysis for RISC processors
    IEEE Transactions on Software Engineering, 1995
    Co-Authors: Sung-soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, Soo-mook Moon, Chong Sang Kim
    Abstract:

    An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real time systems. In RISC processors, the execution time of a Program Construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, we propose extensions to the original timing schema where the timing information associated with each Program Construct is a simple time bound. In our approach, associated with each Program Construct is worst case timing abstraction, (WCTA), which contains detailed timing information of every execution path that might be the worst case execution path of the Program Construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across Program Constructs. The paper also reports on preliminary results of WCET analysis for a RISC processor. Our results show that tight WCET bounds (within a maximum of about 30% overestimation) can be obtained by using the revised timing schema approach. >

  • RTSS - An accurate worst case timing analysis technique for RISC processors
    Proceedings Real-Time Systems Symposium REAL-94, 1994
    Co-Authors: Sung-soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, Choug Sang Kim
    Abstract:

    An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real-time systems. In RISC processors, the execution time of a Program Construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, this paper proposes extensions of the original timing schema (Shaw, 1989) where the timing information associated with each Program Construct is a simple time-bound. We associate with each Program Construct what we call a WCTA (Worst Case Timing Abstraction), which contains detailed timing information of every execution path that might be the worst case execution path of the Program Construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time-bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across Program Constructs. This paper also reports on preliminary results of WCET analyses for a pipelined processor. Our results show that up to 50% tighter WCET bounds can be obtained by using the revised timing schema. >

  • RTSS - A worst case timing analysis technique for multiple-issue machines
    Proceedings 19th IEEE Real-Time Systems Symposium (Cat. No.98CB36279), 1
    Co-Authors: Sung-soo Lim, Jung Hee Han, Jihong Kim, Sang Lyul Min
    Abstract:

    We propose a worst case timing analysis technique for in-order multiple-issue machines. In the proposed technique, timing information for each Program Construct is represented by a directed acyclic graph (DAG) that shows dependences among instructions in the Program Construct. From this information, we derive for each pair of instructions the distance bounds between their issue times. Using these distance bounds, we identify the sets of instructions that can be issued at the same time. Deciding such instructions is an essential task in reasoning about the timing behavior of multiple-issue machines. In order to reduce the complexity of analysis, the distance bounds are progressively refined through a hierarchical analysis over the Program syntax tree in a bottom-up fashion. Our experimental results show that the proposed technique can predict the worst case execution times for in-order multiple-issue machines as accurately as ones for simpler RISC processors.

Jeffrey Scott Vitter - One of the best experts on this subject based on the ideXlab platform.

  • Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments
    Information and Computation, 1996
    Co-Authors: K. Romanik, Jeffrey Scott Vitter
    Abstract:

    AbstractWe examine the complexity of testing different Program Constructs. We do this by defining a measure of testing complexity known as VCP-dimension, which is similar to the Vapnik–Chervonenkis dimension, and applying it to classes of Programs, where all Programs in a class share the same syntactic structure. VCP-dimension gives bounds on the number of test points needed to determine that a Program is approximately correct, so by studying it for a class of Programs we gain insight into the difficulty of testing the Program Construct represented by the class. We investigate the VCP-dimension of straight line code, if–then–else statements, and for loops. We also compare the VCP-dimension of nested and sequential if–then–else statements as well as that of two types of for loops with embedded if–then–else statements. Finally, we perform an empirical study to estimate the expected complexity of straight line code

  • COMPSAC - Using computational learning theory to analyze the testing complexity of Program segments
    Proceedings of 1993 IEEE 17th International Computer Software and Applications Conference COMPSAC '93, 1
    Co-Authors: K. Romanik, Jeffrey Scott Vitter
    Abstract:

    We examine the complexity of testing different Program Constructs by defining a measure called VCP-dimension and applying it to classes of Programs, where all Programs in a class share the same syntactic structure. VCP-dimension gives bounds on the number of test points needed to determine approximate correctness, so it gives insight into the difficulty of testing a Program Construct represented by a Program class. We investigate the VCP-dimension of straight line code, if-then-else statements and for loops, and we compare the VCP-dimension of different combinations of Constructs. >

Choug Sang Kim - One of the best experts on this subject based on the ideXlab platform.

  • RTSS - An accurate worst case timing analysis technique for RISC processors
    Proceedings Real-Time Systems Symposium REAL-94, 1994
    Co-Authors: Sung-soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, Choug Sang Kim
    Abstract:

    An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real-time systems. In RISC processors, the execution time of a Program Construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, this paper proposes extensions of the original timing schema (Shaw, 1989) where the timing information associated with each Program Construct is a simple time-bound. We associate with each Program Construct what we call a WCTA (Worst Case Timing Abstraction), which contains detailed timing information of every execution path that might be the worst case execution path of the Program Construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time-bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across Program Constructs. This paper also reports on preliminary results of WCET analyses for a pipelined processor. Our results show that up to 50% tighter WCET bounds can be obtained by using the revised timing schema. >

Sang Lyul Min - One of the best experts on this subject based on the ideXlab platform.

  • An accurate worst case timing analysis for RISC processors
    1995
    Co-Authors: Sung-soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, Soo-mook Moon, Chong Sang Kim
    Abstract:

    An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real-time systems. In RISC processors, the execution time of a Program Construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, we propose extensions to the original timing schema where the timing information associated with each Program Construct is a simple time-bound. In our approach, associated with each Program Construct is worst case timing abstraction, (WCTA), which contains detailed timing information of every execution path that might be the worst case execution path of the Program Construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time-bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across Program Constructs. This paper also reports on preliminary results of WCET analysis for a RISC processor. Our results show that tight WCET bounds (within a maximum of about 30% overestimation) can be obtained by using the revised timing schema approach.

  • An accurate worst case timing analysis for RISC processors
    IEEE Transactions on Software Engineering, 1995
    Co-Authors: Sung-soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, Soo-mook Moon, Chong Sang Kim
    Abstract:

    An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real time systems. In RISC processors, the execution time of a Program Construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, we propose extensions to the original timing schema where the timing information associated with each Program Construct is a simple time bound. In our approach, associated with each Program Construct is worst case timing abstraction, (WCTA), which contains detailed timing information of every execution path that might be the worst case execution path of the Program Construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across Program Constructs. The paper also reports on preliminary results of WCET analysis for a RISC processor. Our results show that tight WCET bounds (within a maximum of about 30% overestimation) can be obtained by using the revised timing schema approach. >

  • RTSS - An accurate worst case timing analysis technique for RISC processors
    Proceedings Real-Time Systems Symposium REAL-94, 1994
    Co-Authors: Sung-soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, Choug Sang Kim
    Abstract:

    An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real-time systems. In RISC processors, the execution time of a Program Construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, this paper proposes extensions of the original timing schema (Shaw, 1989) where the timing information associated with each Program Construct is a simple time-bound. We associate with each Program Construct what we call a WCTA (Worst Case Timing Abstraction), which contains detailed timing information of every execution path that might be the worst case execution path of the Program Construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time-bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across Program Constructs. This paper also reports on preliminary results of WCET analyses for a pipelined processor. Our results show that up to 50% tighter WCET bounds can be obtained by using the revised timing schema. >

  • A worst case timing analysis technique for instruction prefetch buffers
    Microprocessing and Microprogramming, 1994
    Co-Authors: Minsuk Lee, Sang Lyul Min, Chong Sang Kim
    Abstract:

    Predictable performance is crucial for real-time computing systems. We propose a buffered threaded prefetch scheme as a predictable and high performance instruction memory hierarchy. We also give extensions to the timing schema[3] to analyze the timing effects of the proposed scheme. In the extended timing schema, we associate with each Program Construct what we call a WCTA (Worst Case Timing Abstraction), which contains detailed timing information of the Program Construct. By defining a concatenation operation on WCTAs, our revised timing schema accurately accounts for the timing effects of the buffered threaded prefetching not only within but also across Program Constructs. This paper shows, through analysis using a timing tool based on the extended timing schema, the buffered prefetch scheme significantly improves the worst case execution times of tasks.

  • RTSS - A worst case timing analysis technique for multiple-issue machines
    Proceedings 19th IEEE Real-Time Systems Symposium (Cat. No.98CB36279), 1
    Co-Authors: Sung-soo Lim, Jung Hee Han, Jihong Kim, Sang Lyul Min
    Abstract:

    We propose a worst case timing analysis technique for in-order multiple-issue machines. In the proposed technique, timing information for each Program Construct is represented by a directed acyclic graph (DAG) that shows dependences among instructions in the Program Construct. From this information, we derive for each pair of instructions the distance bounds between their issue times. Using these distance bounds, we identify the sets of instructions that can be issued at the same time. Deciding such instructions is an essential task in reasoning about the timing behavior of multiple-issue machines. In order to reduce the complexity of analysis, the distance bounds are progressively refined through a hierarchical analysis over the Program syntax tree in a bottom-up fashion. Our experimental results show that the proposed technique can predict the worst case execution times for in-order multiple-issue machines as accurately as ones for simpler RISC processors.

K. Romanik - One of the best experts on this subject based on the ideXlab platform.

  • Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments
    Information and Computation, 1996
    Co-Authors: K. Romanik, Jeffrey Scott Vitter
    Abstract:

    AbstractWe examine the complexity of testing different Program Constructs. We do this by defining a measure of testing complexity known as VCP-dimension, which is similar to the Vapnik–Chervonenkis dimension, and applying it to classes of Programs, where all Programs in a class share the same syntactic structure. VCP-dimension gives bounds on the number of test points needed to determine that a Program is approximately correct, so by studying it for a class of Programs we gain insight into the difficulty of testing the Program Construct represented by the class. We investigate the VCP-dimension of straight line code, if–then–else statements, and for loops. We also compare the VCP-dimension of nested and sequential if–then–else statements as well as that of two types of for loops with embedded if–then–else statements. Finally, we perform an empirical study to estimate the expected complexity of straight line code

  • {\bf (Revision of CS-1993-27.)} Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments
    1994
    Co-Authors: K. Romanik, Scott J Vitter
    Abstract:

    We examine the complexity of testing different Program Constructs. We do this by defining a measure of testing complexity known as VCP-dimension, which is similar to the Vapnik-Chervonenkis dimension, and applying it to classes of Programs, where all Programs in a class share the same syntactic structure. VCP-dimension gives bounds on the number of test points needed to determine that a Program is approximately correct, so by studying it for a class of Programs we gain insight into the difficulty of testing the Program Construct represented by the class. We investigate the VCP-dimension of straight line code, if-then-else statements, and for loops. We also compare the VCP-dimension of nested and sequential if-then-else statements as well as that of two types of for loops with embedded if-then-else statements. Finally, we perform an empirical study to estimate the expected complexity of straight line code.

  • COMPSAC - Using computational learning theory to analyze the testing complexity of Program segments
    Proceedings of 1993 IEEE 17th International Computer Software and Applications Conference COMPSAC '93, 1
    Co-Authors: K. Romanik, Jeffrey Scott Vitter
    Abstract:

    We examine the complexity of testing different Program Constructs by defining a measure called VCP-dimension and applying it to classes of Programs, where all Programs in a class share the same syntactic structure. VCP-dimension gives bounds on the number of test points needed to determine approximate correctness, so it gives insight into the difficulty of testing a Program Construct represented by a Program class. We investigate the VCP-dimension of straight line code, if-then-else statements and for loops, and we compare the VCP-dimension of different combinations of Constructs. >