Scalability Test

The following three experiments have been conducted to evaluate the scalability of Next Release Tool:

  1. Scalability with respect to problem size:

    2. In order to figure out how the tool scales with respect to the size of the problem (i.e. number of model elements in our case), An initial model consists of 13 goal nodes, 9 refinements and 4 inter-dependences has been created, and replicated  from 10 to 750 times to generate  75 experimental cases.  By running each case 5 times we identify a linear relationship between the problem size and the time it took to reason on the model.

    ScalabilityWithRespectToProblemSizeModel (10.1 KiB)

  2. Scalability with respect to problem complexity:

    3. In order to understand how the tool behaves as the number of inter-dependencies increase, we generated 400 test cases by increasing the number of directed inter-dependencies in a fixed size model. Our initial model had 250 goal nodes, 118 refinement nodes, 16 precedence, and 16 exclusions. For each run, an increasing number of random directed inter-dependencies are placed between randomly selected goal nodes from the original model. From this experiment we realize  a smooth increase in reasoning time until approximately 150 inter-dependencies, and the reasoning time increases rapidly after this threshold.

    ScalabilityWithRespectToProblemComplexityModel (172.3 KiB)

  3. Scalability with respect to alternatives:

    4. In order to test the scalability of the tool against the number of alternative solutions in a model, we created five model variations with fixed number of goals and inter-dependencies, 11918 and 1402, respectively. In the first model, all 5609 refinement elements had two incoming edges, and a parent goal had only one incoming refinement edge. This setup corresponds to having all AND decompositions. For the second variation, we have started with the first model, but for the 25% refinement elements, we have created another refinement element pointing to the same parent goal, and directed one of the two incoming edges of the original refinement element to the newly created one, in other words, we have converted 25% of the AND decompositions to OR decompositions. For the rest of the variations, we have increased the conversion rate to 50%, 75%, and finally 100%. From this experiment we recognize that when the number of alternative solutions increases in a problem,   the reasoning time will also grow together.

    ScalabilityWithRespectToAlternatives 0% (12.0 KiB)

    ScalabilityWithRespectToAlternatives 25% (12.0 KiB)

    ScalabilityWithRespectToAlternatives 50% (12.1 KiB)

    ScalabilityWithRespectToAlternatives 75% (12.1 KiB)

    ScalabilityWithRespectToAlternatives 100% (12.1 KiB)