mdh.sePublications
Change search
Refine search result
1 - 13 of 13
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 1.
    Gustafsson, Jan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Sandberg, Christer
    Mälardalen University, School of Innovation, Design and Engineering.
    Källberg, Linus
    Mälardalen University, School of Innovation, Design and Engineering.
    ALF - A Language for WCET Flow Analysis2009In: OpenAccess Series in Informatics Volume 10, 2009, 2009Conference paper (Refereed)
    Abstract [en]

    Static Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component in static WCET analysis is the flow analysis, which derives bounds on the number of times different code entities can be executed. Examples of flow information derived by a flow analysis are loop bounds and infeasible paths. Flow analysis can be performed on source code, intermediate code, or binary code: for the latter, there is a proliferation of instruction sets. Thus, flow analysis must deal with many code formats. However, the basic flow analysis techniques are more or less the same regardless of the code format. Thus, an interesting option is to define a common code format for flow analysis, which also allows for easy translation from the other formats. Flow analyses for this common format will then be portable, in principle supporting all types of code formats which can be translated to this format. Further, a common format simplifies the development of flow analyses, since only one specific code format needs to be targeted. This paper presents such a common code format, the ALF language (ARTIST2 Language for WCET Flow Analysis).

  • 2.
    Holsti, N.
    et al.
    Tidorum Ltd., Helsinki, Finland.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Källberg, Linus
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Analysing switch-case code with abstract execution2015In: OpenAccess Series in Informatics, 2015, p. 85-94Conference paper (Refereed)
    Abstract [en]

    Constructing the control-flow graph (CFG) of machine code is made difficult by dynamic transfers of control (DTC), where the address of the next instruction is computed at run-time. Switchcase statements make compilers generate a large variety of machine-code forms with DTC. Two analysis approaches are commonly used: pattern-matching methods identify predefined instruction patterns to extract the target addresses, while analytical methods try to compute the set of target addresses using a general value-Analysis. We tested the abstract execution method of the SWEET tool as a value analysis for switch-case code. SWEET is here used as a plugin to the Bound-T tool: thus our work can also be seen as an experiment in modular tool design, where a general value-Analysis tool is used to aid the CFG construction in a WCET analysis tool. We find that the abstract-execution analysis works at least as well as the switch-case analyses in Bound-T itself, which are mostly based on pattern-matching. However, there are still some weaknesses: the abstract domains available in SWEET are not well suited to representing sets of DTC target addresses, which are small but sparse and irregular. Also, in some cases the abstract-execution analysis fails because the used domain is not relational, that is, does not model arithmetic relationships between the values of different variables. Future work will be directed towards the design of abstract domains eliminating these weaknesses.

  • 3.
    Holsti, Niklas
    et al.
    Tidorum LTD, Finland.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Källberg, Linus
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Combining Bound-T and SWEET to Analyse Dynamic Control Flow in Machine-Code Programs2014Report (Other academic)
    Abstract [en]

    The first step in the static analysis of a machine-code subprogram is to construct the control-flow graph. The typical method is to start from the known entry-point address of the subprogram, retrieve and decode the instruction at that point, insert it in the control-flow graph, determine the address(es) of the successor instruction(s) from the known semantics of the instruction set, and repeat the process for the successor instructions until all reachable instructions and control flows are discovered and entered in the control-flow graph. This procedure is straight-forward as long as the successors of each instruction are statically defined. However, most instruction sets allow for dynamically determined successors, usually by allowing the target address of a branch to be set by the run-time, dynamically computed value of a register. We call such instructions dynamic branches. To construct the control-flow graph, a static analyser must somehow discover the possible values of the target address, in other words, it must perform a value-analysis of the program. This is problematic for two reasons. Firstly, the value-analysis must be applied to an incomplete control-flow graph, which means that the value-analysis will also be incomplete, and may be an under-estimate of the value-set for the complete subprogram. Second, value-analyses typically over-estimate the value-set, which means that the set of possible target addresses of the dynamic branch may be over-estimated, which leads to an over-estimate of the control- flow graph. The over-estimated graph may include instructions and control flows that do not really belong to the subprogram under analysis. This report describes how we connected two analysis tools, Bound-T from Tidorum Ltd and SWEET from Mälardalen University, so that the powerful "abstract execution" analysis in SWEET can be invoked from Bound-T to resolve dynamic branches that Bound-T finds in the machine-code program under analysis. The program-representation language ALF, defined by the SWEET group, is used as an interface language between Bound-T and SWEET. We evaluate the combined analysis on example programs, including both synthetic and real ones, and conclude that the approach is promising but not yet a great improvement. Bound-T contains several special-case analyses for dynamic branches, which currently perform slightly better than SWEET's more general analyses. However, planned improvements to SWEET may result in an analysis which is at least as powerful but more robust than the analyses in Bound-T alone.

  • 4.
    Källberg, Linus
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. IS (Embedded Systems).
    Circular Linear Progressions in SWEET2014Report (Other academic)
    Abstract [en]

    The SWEET tool offers numerous static program analyses based on abstract interpretation, such as value analyses and a variety of flow analyses. For a long time, the main abstract domain used in SWEET to represent sets of concrete integers has been an interval domain that can model the wraparound behavior of fixed-precision arithmetic. Although this domain is made attractive by its simplicity, it cannot abstract sparse value sets with sufficient precision. Sparse value sets in which the elements are separated by a constant stride commonly occur, e.g., when analyzing array accesses to derive the possible byte offsets into the array. To improve the accuracy of SWEET's analyses in such situations, we extended SWEET with a variant of Sen and Srikant's domain of Circular Linear Progressions, which keeps stride information together with the interval bounds. This report describes our implementation, in which we improved the expressiveness of the original domain by lifting some restrictions on the parameters defining the objects of the domain.

  • 5.
    Källberg, Linus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Larsson, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    Ray Tracing using Hierarchies of Slab Cut Balls2010In: Eurographics 2010, short papers, 2010, p. 69-72Conference paper (Refereed)
    Abstract [en]

    In this paper, bounding volume trees of slab cut balls are evaluated and compared with other types of trees for raytracing. A novel tree construction algorithm is proposed, which utilizes a relative orientation heuristic betweenparent and child nodes. Also, a fast intersection test between a ray and a slab cut ball is presented. Experimentalcomparisons to other commonly used enclosing shapes reveal that the slab cut ball is attractive. In particular, theslab cut ball outperforms the sphere in all tested scenes with speed-up factors between 1 and 4.

  • 6.
    Källberg, Linus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Larsson, Thomas B
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    A Filtering Heuristic for the Computation of Minimum-Volume Enclosing Ellipsoids2016In: Lecture Notes in Computer Science,, Hong Kong, China: Springer International Publishing , 2016, p. 744-753Conference paper (Refereed)
    Abstract [en]

    We study heuristics to accelerate existing state-of-the-art algorithms for the minimum-volume enclosing ellipsoid problem. We propose a new filtering heuristic that can significantly reduce the number of distance computations performed in algorithms derived from Khachiyan’s first-order algorithm. Our experiments indicate that in high dimensions, the filtering heuristic is more effective than the elimination heuristic proposed by Harman and Pronzato. In lower dimensions, the elimination heuristic is superior.

  • 7.
    Källberg, Linus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Larsson, Thomas B
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Accelerated Computation of Minimum Enclosing Balls by GPU Parallelization and Distance Filtering2014In: Proceedings of SIGRAD 2014 SIGRAD 2014, 2014Conference paper (Refereed)
    Abstract [en]

    Minimum enclosing balls are used extensively to speed up multidimensional data processing in, e.g., machine learning, spatial databases, and computer graphics. We present a case study of several acceleration techniques that are applicable in enclosing ball algorithms based on repeated farthest-point queries. Parallel GPU solutions using CUDA are developed for both low- and high-dimensional cases. Furthermore, two different distance filtering heuristics are proposed aiming at reducing the cost of the farthest-point queries as much as possible by exploiting lower and upper distance bounds. Empirical tests show encouraging results. Compared to a sequential CPU version of the algorithm, the GPU parallelization runs up to 11 times faster. When applying the distance filtering techniques, further speedups are observed.

  • 8.
    Källberg, Linus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Larsson, Thomas B
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Faster Approximation of Minimum Enclosing Balls by Distance Filtering and GPU Parallelization2015In: Journal of Graphics Tools, ISSN 2165-3488, Vol. 17, no 3, p. 67-84Article in journal (Refereed)
    Abstract [en]

    Minimum enclosing balls are used extensively to speed up multidimensional data processing in, e.g., machine learning, spatial databases, and computer graphics. We present a case study of several acceleration techniques that are applicable in enclosing ball algorithms based on repeated farthest-point queries. Two different distance filtering heuristics are proposed aiming at reducing the cost of the farthest-point queries as much as possible by exploiting lower and upper distance bounds. Furthermore, auto-tunable GPU solutions using CUDA are developed for both low- and high-dimensional cases. Empirical tests apply these techniques to two recent algorithms and demonstrate substantial speedups of the ball computations. Our results also indicate that a combination of the approaches has the potential to give further performance improvements.

  • 9.
    Källberg, Linus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Larsson, Thomas B
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Improved pruning of large data sets for the minimum enclosing ball problem2014In: Graphical Models, ISSN 1524-0703, E-ISSN 1524-0711, Vol. 76, no 6, p. 609-619Article in journal (Refereed)
    Abstract [en]

    Minimum enclosing ball algorithms are studied extensively as a tool in approximation and classification of multidimensional data. We present pruning techniques that can accelerate several existing algorithms by continuously removing interior points from the input. By recognizing a key property shared by these algorithms, we derive tighter bounds than have previously been presented, resulting in twice the effect on performance. Furthermore, only minor modifications are required to incorporate the pruning procedure. The presented bounds are independent of the dimension, and empirical evidence shows that the pruning procedure remains effective in dimensions up to at least 200. In some cases, performance improvements of two orders of magnitude are observed for large data sets. © 2014 Elsevier Inc. All rights reserved.

  • 10.
    Källberg, Linus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Shellshear, E.
    Fraunhofer Chalmers Centre, Gothenburg, Sweden .
    Larsson, Thomas B
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    An external memory algorithm for the minimum enclosing ball problem2016In: VISIGRAPP 2016 - Proceedings of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications, 2016, p. 83-90Conference paper (Refereed)
    Abstract [en]

    In this article we present an external memory algorithm for computing the exact minimum enclosing ball of a massive set of points in any dimension. We test the performance of the algorithm on real-life three-dimensional data sets and demonstrate for the first time the practical efficiency of exact out-of-core algorithms. By use of simple heuristics, we achieve near-optimal I/O in all our test cases.

  • 11.
    Larsson, Thomas B
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Capannini, Gabriele
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Källberg, Linus
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Parallel computation of optimal enclosing balls by iterative orthant scan2016In: Computers & graphics, ISSN 0097-8493, E-ISSN 1873-7684, Vol. 56, p. 1-10Article in journal (Refereed)
    Abstract [en]

    We propose an algorithm for computing the exact minimum enclosing ball of large point sets in general dimensions. It aims to reduce the number of passes by retrieving a well-balanced set of outliers in each linear search through the input by decomposing the space into orthants. The experimental evidence indicates that the convergence rate in terms of the required number of linear passes is superior compared to previous exact methods, and substantially faster execution times are observed in dimensions d≤16. In the important three-dimensional case, the execution times indicate real-time performance. Furthermore, we show how the algorithm can be adapted for parallel execution on both CPU and GPU architectures using OpenMP, AVX, and CUDA. For large datasets, our CUDA solution is superior. For example, the benchmark results show that optimal bounding spheres for inputs with tens of millions of points can be computed in just a few milliseconds.

  • 12.
    Larsson, Thomas B
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Källberg, Linus
    Mälardalen University, School of Innovation, Design and Engineering.
    Fast and robust approximation of smallest enclosing balls in arbitrary dimensions2013In: Computer graphics forum (Print), ISSN 0167-7055, E-ISSN 1467-8659, Vol. 32, no 5, p. 93-101Article in journal (Refereed)
    Abstract [en]

    In this paper, an algorithm is introduced that computes an arbitrarily fine approximation of the smallest enclosing ball of a point set in any dimension. This operation is important in, for example, classification, clustering, and data mining. The algorithm is very simple to implement, gives reliable results, and gracefully handles large problem instances in low and high dimensions, as confirmed by both theoretical arguments and empirical evaluation. For example, using a CPU with eight cores, it takes less than two seconds to compute a 1.001-approximation of the smallest enclosing ball of one million points uniformly distributed in a hypercube in dimension 200. Furthermore, the presented approach extends to a more general class of input objects, such as ball sets. 

  • 13.
    Larsson, Thomas
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Källberg, Linus
    Mälardalen University, School of Innovation, Design and Engineering.
    Fast Computation of Tight-Fitting Oriented Bounding Boxes2011In: Game Engine Gems 2, A K Peters/CRC Press , 2011Chapter in book (Other academic)
1 - 13 of 13
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf