Arne Maus

• Maus, Arne (2015). A full parallel Quicksort algorithm for multicore processors. NIKT: Norsk IKT-konferanse for forskning og utdanning. ISSN 1892-0713.
• Gjessing, Stein & Maus, Arne (2012). Teaching predicates and invariants on shared data structures in concurrent programming. In Gehringer, Edward F. & Brown, Dick (Ed.), SPLASH '12 Conference on Systems, Programming, and Applications: Software for Humanity, Proceedings of the 2012 workshop on Developing competency in parallelism: techniques for education and training. ACM Publications. ISSN 978-1-4503-1840-2. p. 9–14. doi: 10.1145/2414659.2414662.
• Maus, Arne (2011). A full parallel radix sorting algorithm for multicore processors, Norsk Informatikkonferanse NIK 2011. Tapir Akademisk Forlag. ISSN 978-82-519-2843-4. p. 37–48. Full text in Research Archive
• Maus, Arne & Moen Drange, Jon (2010). All closest neighbors are proper Delaunay edges generalized, and its application to parallel algorithms. In Fallmyr, Terje & Hjelmås, Erik (Ed.), Norsk Informatikkonferanse. Tapir Akademisk Forlag. ISSN 978-82-519-2703-1. p. 1–12. Show summary

  In this paper we first prove that for any set of points P in the plane,the closest neighbor b to any point p in P is a proper triangle edge bp in D(P), the Delaunay triangulation of P. We also generalize this result and prove that the j'th (second, third, ..) closest neighbors bj to p are also edges pbj in D(P) if they satisfy simple tests on distances from a point. Even though we can find many of the edges in D(P) in this way by looking at close neighbors, we give a three point example showing that not all edges in D(P) can be found in this way. For a random dataset we give results from test runs and a model that show that our method finds on the average 4 edges per point in D(P). Also, we prove that the Delaunay edges found in this way form a connected graph. We use these results to outline two parallel algorithms for finding D(P). Finally, we comment on using these theorems and solving the k'th closest neighbors problem.

• Maus, Arne & Lingjærde, Ole Christian (2009). LASTING EFFECTS OF AUTOMATIC PLAGIARISM DETECTION IN AN INTRODUCTORY COURSE IN PROGRAMMING. In Gómez Chova, L (Eds.), INTED2009 Proceedings CD. International Academy of Technology, Education and Development (IATED). ISSN 978-84-612-7578-6.
• Maus, Arne & Lingjærde, Ole Christian (2008). The application of a novel plagiarism detection system to an introductory course in programming: lessons learned. In Gómes Chova, I.; Martí Belenguer, D. & Candel Torres, I. (Ed.), INTED2008 IProceedings. International Academy of Technology, Education and Development (IATED). ISSN 978-84-612-0190-7.
• Maus, Arne (2008). IPS, sorting by transforming an array into its own sorting permutation with almost no space overhead. In Sandnes Eika, Frode & Prinz, Andreas (Ed.), Norsk informatikkonferanse NIK 2008. Tapir Akademisk Forlag. ISSN 978-82-519-2386-6. p. 63–74. Show summary

  This paper presents two new algorithms for inline transforming an integer array ‘a’ into its own sorting permutation - that is: after performing either of these algorithms, a[i] is the index in the unsorted input array ‘a’ of its i’th largest element (i=0,1..n-1). The difference between the two IPS (Inline Permutation Substitution) algorithms is that the first and fastest generates an unstable permutation while the second generates the unique, stable, permutation array. The extra space needed in both algorithms is O(log n) – no extra array of length n is needed! The motivation for using these algorithms is given along with their pseudo code. To evaluate their efficiency, they are tested relative to sorting the same array with Quicksort on 4 different machines and for 14 different distributions of the numbers in the input array, with n=10, 50, 250.. 97M. This evaluation shows that both IPS algorithms are generally faster than Quicksort for values of n less than 107, but degenerates both in speed and demand for space for larger values. These are results with 32 bit integers (with 64 bits integers this limit would be proportionally higher, at least 1014 ). The two IPS algorithms do a recursive, most significant digit radix sort (left to right) on the input array while substituting the values of the sorted elements with their indexes.

• Maus, Arne & Gjessing, Stein (2007). A Model for the Effect of Caching on Algorithmic Efficiency in Radix based Sorting. In Dascalu, Sergiu & Dini, Petre (Ed.), ICSEA 2007 (International Conference on Autonomic and Autonomous Systems). IEEE (Institute of Electrical and Electronics Engineers). ISSN 978-0-7695-2937-0.
• Maus, Arne (2007). Buffered Adaptive Radix – a fast, stable sorting algorithm that trades speed for space at runtime when needed. In Sandnes, Frode Eika (Eds.), Norsk informatikkonferanse NIK 2007. Tapir Akademisk Forlag. ISSN 978-82-519-2272-2. p. 19–30.
• Maus, Arne (2006). Making a fast unstable sorting algorithm stable. In Rong, Chunming & Løkketangen, Arne (Ed.), NIK'2006 : Norsk informatikkonferanse. Tapir Akademisk Forlag. ISSN 82-519-2186-4. p. 41–52.
• Gjessing, Stein & Maus, Arne (2005). Discrete Event Simulation of a Large OBS Network. In Jamshidi, Mo (Eds.), Proceedings 2005 IEEE International Conference on Systems, Man and Cybernetics. IEEE (Institute of Electrical and Electronics Engineers).
• Maus, Arne (2005). Research and Curricula Developemnt of Norwegian Universities From the early years to the mid-1970s. In Bubenko, Janis; Impagliazzo, John & Sølvberg, Arne (Ed.), History of Nordic Computing. Springer. ISSN 0-387-24167-1. p. 137–154.
• Gjessing, Stein & Maus, Arne (2002). A Fairness Algorithm for High-speed Networks based on a Resilient Packet Ring Architecture. In El Kamel, Abdelkader (Eds.), 2002 IEEE International Conference on Systems, Man and Cybernetics. IEEE (Institute of Electrical and Electronics Engineers). ISSN 2-9512309-4-X. Full text in Research Archive Show summary

  IEEE is currently standardizing a spatial reuse ring topology network called the Resilient Packet Ring (RPR, IEEE P802.17). The goal of the RPR development is to make a LAN/MAN standard, but also WANs are discussed. A ring network needs a fairness algorithm that regulates each stations access to the ring. The RPR fairness algorithm is currently being developed with mostly long distances between stations in mind. In this paper we discuss the feedback aspects of this algorithm and how it needs to be changed in order to give good performance if and when RPR is used for high-speed networks and LANs with shorter distances between stations. We discuss different architectural parameters including buffers sizes and distances between stations. We suggest the use of triggers instead of timers to meet the response requirements of high-speed networks. We have developed a discrete event simulator in the programming language Java. The proposed improvements are compared and evaluated using a ring network model that we have built using our simulator.

• Maus, Arne (2002). ARL, a faster in-place, cache friendly sorting algorithm. In Stohl, Norvald; Strøm, Torbjørn; Fallmyr, Terje; Haddjerroudit, Sissel; Langmyhr, Dag & Manne, Fredrik (Ed.), Norsk Informatikkonferanse NIK'2002. Universitetet i Sørøst-Norge/Universitetet i Søraust-Noreg. ISSN 82-91116-45-8. p. 85–95.
• Maus, Arne (1996). Vitenskap, informasjonsteknologi, og samfunnsmessige virkninger. In Wormnæs, Odd (Eds.), Vitenskap - enhet og mangfold. Gyldendal Akademisk. ISSN 82-417-0682-0. p. 388–406. Show summary

  Dette kapittelet handler om virkningene av data- og datanettteknologien. Vi skal søke å se på vitenskapens rolle, samfunnsmessige virkninger og etiske dilemma som reiser seg ved anvendelser av IT.

• Maus, Arne (1995). Datavtalene og Arbeidsmilojøloven. IT og arbeidsplassene. Personvern og sikerheten i informasjonssamfunnet. In Hannemyr, Gisle; Maus, Arne; Skagestein, Gerhard M & Sugar, Aud (Ed.), BIT 1 A Brukersystemer. ISSN 82-02-15361-1. p. 46–71. Show summary

  To kapitler i lærebok for videregående skole i IT.

• Maus, Arne (1984). Delanay Triangulation and the Convex Hull of n Points in expected linear Time. BIT Numerical Mathematics. ISSN 0006-3835. 24(37), p. 151–163. Show summary

  An algorith is presented which produces a Delaunay triangulation of n points in the Euclidean plane in expexted linear time. The expected execution time is acheived when the data are (not too far from) uniformly distributed. A modification of the algorithm discussed in the appendix, treats most of the non-uniform distributions. The basis of this algorithm is a geographical partitioning of the plan into boxes by the well-known Radix algorithm. This partiotioning is also used as a basis for a linear time algorithm for finding the convex hull of n points in the Euclidean plane.

• Maus, Arne (1982). Technology and Employment. In Forrum, Eystein (Eds.), Computerization of Working Life. Ellis Horwood limited, Chirhester. ISSN 0-85312-584-8. p. 61–84. Show summary

  The question of wheather EDP has an impact on employment, is one of the most cotroversial issues concerning the social impact of technology.

• Maus, Arne & Endresen, Jan (1979). Misuse of computer-generated results. Medical and Biological Engineering and Computing. ISSN 0140-0118. p. 126–129. Show summary

  The number of statistical tests performed has increased by several orders of magnitude through the use of computers and read-made statistical packages. The vast majority of these tests neither physically can be, nor ever are, published. Only tests which show a strog statistical corrolation between some variables seems to be sorted out for publication. This practice, which can be found in applied sciences such as social and medical sciences, is investigated and shown in many cases to lesd to a considerable increase in the percentage of published false results. A new function to be perormed by statistical packages is then proposed to reduce theis percentage.

• Maus, Arne (1975). On Access to Temporary Resources. BIT Numerical Mathematics. ISSN 0006-3835. 15(1), p. 72–84. Show summary

  The sharable resources of a multiprogramming system can be classified as either permanent or temporary, and their use can be classified as either exclusive or non-exclusive. While semaphores, as defined by Dijkstra syncronize access to permanent resources, this article proposes two new primitives for synchronize access to temporary resources. Theis usefullness is demonstrated by examining the problem of a number of 'readers' and 'writers' sharing a single file. Finally, a high-level language notation is proposed which synchronizes access to a declared, sharable resource of any of the categories classified above.

View all works in Cristin

• Maus, Arne & Gjessing, Stein (2014). Practical Parallel Programming – a B.S. course on how to design an efficient parallel algorithm. EduPar14. ISBN 978-1-4799-4117-9. 8 p.
• Brunland, Anders; Hegna, Knut; Lingjærde, Ole Christian & Maus, Arne (2011). Rett på Java - 3.utg. Universitetsforlaget. ISBN 978-82-15-01852-2. 390 p.
• Brunland, Anders; Hegna, Knut; Lingjærde, Ole Christian & Maus, Arne (2005). Rett på Java, 2 utg. Universitetsforlaget. ISBN 82-15-00781-3. 363 p.
• Brunland, Anders; Hegna, Knut; Lingjærde, Ole Christian & Maus, Arne (2003). Rett på Java. Universitetsforlaget. ISBN 82-15-00257-9. 280 p.
• Hannemyr, Gisle; Maus, Arne; Skagestein, Gerhard M & Sugar, Aud (1995). BIT 1 A Brukersystemer. ISBN 82-02-15361-1.

View all works in Cristin

• Maus, Arne; Gulli, Thomas & Jul, Eric Bartley (2020). Some Faster Algorithms for Finding Large Prime Gaps.
• Maus, Arne (2019). RadixInsert, a much faster stable algorithm for sorting floating-point numbers.
• Maus, Arne (2018). A faster, all parallel Merge sort algorithm for multicore processors.
• Maus, Arne (2002). PRP - Parallel Recursive Procedures, a low cost, easy to use alternative for some often ocurring classes of problems. Show summary

  Almost all work on parallelizing programs uses the abstraction of communicating parallel programs in the form of processes or parallel threads. This lecture presents an alternative abstraction - parallelizing a problem though the use of a recursive procedure (PRP). With this PRP concept the recursion tree is split among all participating machines (connected by a LAN or Web). The user involvement in this process is minimal by just putting in two different comments in the original recursive program. What restrictions that has to be put on the recursive procedure in PRP is presented along with a sketch of the implementation and examples on problems solved. This concept is demonstrated to scale very well up to 120 machines (max. tried so far) and for some interesting classes of problems. This is a report from an ongoing series of master thesis at the Dept. of Informatics, Univ. of Oslo, which now has produced a well working Java based platform for the PRP system.

• Maus, Arne (2002). Two 'new' sorting algorithms - and the effect of multi level caching on performance. Show summary

  This presentation introduces two new, fast sorting algoritms: MSort and Psort, both having advantages (in-place re-ordering and generating the sorting permutation). Both are significantly faster then Quicksort. MSort is a modified Most Significant Radix algorithm. PSort is a fast way to generate the permutation p that defines the sorting order of a set of integer keys in an integer array ¿a¿- that is: a[p[i]] is the i¿th sorted element in ascending order. The motivation for using Psort is given along with its implementation in Java. This distribution based sorting algorithm, Psort, is compared to two comparison based algorithms, Heapsort and Quicksort, and two other distribution based algorithms, Bucket sort and Radix sort. The relative performance of the distribution sorting algorithms for arrays larger than a few thousand elements are assumed to be caused by how well they handle caching (both level 1 and level 2). The effect of caching is investigated, and based on these results, more cache friendly versions of Psort and Radix sort are presented and compared.

• Maus, Arne (2000). Sorting by generating the sorting partition, and the effect of caching on sorting. Show summary

  This paper presents a fast way to generate the permutation p that defines the sorting order of a set of integer keys in an integer array 'a' - that is: a[p[i]] is the i'th sorted element in ascending order. The motivation for using Psort is given along with its implementation in Java. This distribution based sorting algorithm is compared to two comparison based algortthms, Heapsort and Quicksort, and two other distribution based algorithms, Bucket sort and Radix sort. The relative performance of the distribution sorting algorithms for arrays larger then a few thousand elements are assumed to be caused by how well they handle caching (both level 1 and 2). The effect of caching is invesitgated, and based on these results, more cache friendly versions of Psort and Radix sort are presented and compared.

• Maus, Arne (1999). Klynger av PC-er, framtidas superdatamaskiner. Show summary

  Oversikt over potensielle hastighetsforbedringer og programvare for å å koble tett sammen et antall PCer

• Maus, Arne (1999). Objektorientert systemutvikling. Show summary

  Grunnleggende innføring i begreper, metoder og anvendelser.

• Strøm, Torstein; Halfen, Bjørn; Maus, Arne & Gjessing, Stein (1999). A HIC based SCI switch - implementation and performance. Show summary

  This paper describes a prototype switching unit that translates IEEE 1596 SCI packets to and from the serial IEEE 13555 HIC technology. The unit has one SCI interface and twelve HIC interfaces. Up to seven of these units can be placed back-to-back to make up an SCI switch. Hardware and system behaviour is described. Latency and throughput are presented for different configurations and different sizes of user data. Finally the potential of an industrial version of this prototype is evaluated.

• Gjessing, Stein; Maus, Arne; Strøm, Torstein & Huse, Lars Paul (1999). Running the Synthetic Aperture Radar (SAR) Application on a switched SCI cluster. Show summary

  We describe how a real application, the Syntetic Aperture Radar (SAR) program, is parallelized and run on a cluster of PCs connected by SCI. We have a prototype SCI switch that uses the serial IEEE 1355 HIC technology in its switching fabric. The prototype switch can not keep up with the speed of the SCI interconnect, and we analyze and discuss how switch performance influence the execution time of our parallelized application.

• Strøm, Torstein; Maus, Arne; Halfen, Bjørn & Gjessing, Stein (1999). A HIC Based SCI switch - implementation and performance. Show summary

  This paper describes a prototype switching unit that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. The unit has one SCI interface and twelve HIC interfaces. Up to seven of these units can be placed back-to-back to make up an SCI switch. Hardware and system behaviour is described. Latency and throughput are presented for different configurations and different sizes of user data. Finally the potential of an industrial version of this prototype is evaluated.

• Maus, Arne; Strøm, Torstein; Gjessing, Stein & Huse, Lars Paul (1999). Running the SAR Application on a Cluster of PCs Connected with SCI using a HIC based SCI switch. Show summary

  This paper describes a prototype SCI-switch and its behaviour in a real application. The switching fabric uses the IEEE 1355 HIC technology to switch SCI packets in a switch with up to seven SCI ports. In our lab we have tested a switch with up to three SCI ports. We report on the performance of a Synthetic Aperture Radar (SAR)-application when it is run on a number of dual processor PCs connected by SCI and using our HIC-based SCI switch.

• Maus, Arne; Strøm, Torstein; Gjessing, Stein & Huse, Lars Paul (1999). Running the SAR-application on a cluster of PCs connected with SCI, using a HIC-based SCI-switch. Show summary

  This paper first describes testing of the HIC based SCI switch embedded in a cluster of PCs running standard micro benchmarks (ping-pong latency and throughput) of various data packet sizes and with various configurations of 2 and 3 switched SCI rings. The switch itself is made up of switching units that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. The limitations of this prototype switch are then discussed. A real industrial application, the SAR (Synthetic Aperture Radar) application was run through the switch connected as a 3-way switch, varying the number of nodes in each switched SCI ring. This paper concludes with a discussion of the viability of an industrial version of this switch.

• Ryan, Stein Jørgen; Maus, Arne & Gjessing, Stein (1997). An operating system independent driver for an I/O based SCI interface.
• Sjøberg, Dag; Jørgensen, Magne & Maus, Arne (1996). Evaluating Software Maintenance Technology.
• Maus, Arne & Aas, Torfinn (1995). PRP - Parallel Recursive Procedures. Show summary

  It is believed that writing parallel programs is hard. Therefore a pradigm for writing parallel programs that is not much harder than writing a sequeltial program is in demand. This paper describes a general method for parallelizing programs based on the idea of using recursive procedures as the grain of parallelism (PRP). This paradigm only adds a few new constructs to an ordinary sequential program with recursive procedures and makes both the underlying hardware topology and in most cases also the number of independant processing nodes, transparent to the programmer. The implementation reported in this paper uses workstations and servers connected to an Ethernet. The efficiency achieved by the PRP-concept must be said to be good with a more than 50% processor utilization on the two problems reported. Other implementatons of the PRP-paradigm is also reported.

• Jørgensen, Magne & Maus, Arne (1993). A case study of software maintenance tasks.
• Maus, Arne (1992). Solutions to a trivial problem - a study in programming paradigms. Show summary

  The complexity theories of programming seek to find and classify the best algorithms for a given problem. This paper has a different perpective. The 'natural' solutions to a trivial problem (finding the sum of the n first natural numbers) are investigated, And it is demonstrated that there is an extreme variation in the time and space efficiency in the solutions we get when following dominant programming styles. This paper can both be used as a student tutorial and be seen as a criticism of some of the more popular programming paradigms.

• Maus, Arne (1992). Entropy as a Complexity Measure, and the Optimal Module Size of Object Oriented Programs. Show summary

  This paper defines a measure for the complexity of a program and its components as seen from a maintenance programmer point of view. This is done by using the entropy measure from thermodynamics. It is shown that two programmes solving the same problem differ considerably in entropy - the program properly structured into classes and procedures having the lowest entropy. The optimal number of procedures and classes is derived. This complexity measure can easily be built into any compiler.

• Maus, Arne (1991). Entropy as a Complexity Measure, and the Optimal Module Size of Object Oriented Programs. Show summary

  This paper defines a measure for the complexity of a program and its components as seen from a maintenance programmer point of view. This is done by using the entropy measure from thermodynamics. It is shown that two programmes solving the same problem differ considerably in entropy - the program properly structured into classes and procedures having the lowest entropy. The optimal number of procedures and classes is derived. This complexity measure can easily be built into any compiler.

• Thoresen, Kari Trædal & Maus, Arne (1979). Technological unemployment and working conditions in the comuterized office - two problem areas for trade unions.
• Maus, Arne (1978). Interlude on Signals and Semaphores Revisited. Communications of the ACM. ISSN 0001-0782. 21(7), p. 592–592.
• Opdal, Lars-Erik; Maus, Arne & Stray, Viktoria (2016). Parallelle beregninger med MPI i delt og distribuert minne. Universitetet i Oslo.
• Maus, Arne; Strøm, Torstein; Gjessing, Stein & Huse, Lars Paul (1999). Final report on the testing of the SCI to HIC switch & Running the SAR (Synthetic Aperture Radar) application in a switched cluster of PCs. ESPRIT/OMI. Show summary

  This combined delivery first describes testing of a HIC based SCI switch embedded in a cluster of PCs running standard micro benchmarks (ping-pong latency and throughput) of various data packet sizes and with various configurations of 2 and 3 switched SCI rings. The switch itself is made up of switching units that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology and is more thoroughly described in D4.1.1 and D 4.1.2 and the micro benchmarks has in more detail been reported in D4.1.4 and D4.1.5. The limitations of this prototype switch are then discussed. After these initial tests, a real industrial application, the SAR (Synthetic Aperture Radar) application was run through the switch connected as a 3-way switch, varying the number of nodes in each switched SCI rings. This deliverable concludes with a discussion of the viability of an industrial version of this switch.

• Strøm, Torstein; Halfen, Bjørn; Maus, Arne & Gjessing, Stein (1999). Working SCI switch based on HIC components. ESPRIT/OMI. Show summary

  This paper describes a prototype switching unit that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. The unit has one SCI interface and twelve HIC interfaces. Up to seven of these units can be placed back-to-back to make up an SCI switch. Hardware and system behaviour is described. Latency and throughput are presented for different configurations and different sizes of user data. Finally the potential of an industrial version of this prototype is evaluated.

• Strøm, Torstein; Halfen, Bjørn; Maus, Arne & Gjessing, Stein (1999). Switched embedded workstation cluster exploiting the HIC based SCI switch. ESPRIT/OMI. Show summary

  This report describes performance characteristics of an experimental HIC based SCI switch embedded in a cluster of PCs. Internally the switch translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. Architectually up to seven SCI rings can be connected to the switch, but due to limited resources, only a 2x2 and a 3x3 switch has been tested. This deliverable focuses on presenting a comprehensive set of low level latency and throughput figures for different configurations, and evaluating the state of this prototype switch and the potentials of an industrial version of this switch.

• Krogdahl, Bjørn & Maus, Arne (1978). Offentlige etaters anskaffelse av EDB-systemer. ISSN 82-539-0075-9.

View all works in Cristin