Tags:
object orientation,
Algorithms,
Parallel programming,
sorting
Publications
-
-
-
-
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
(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
(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.
-
-
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
(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
Published
Nov. 4, 2010 2:08 PM
- Last modified
May 22, 2019 11:54 AM