BIBSYS: Open Journals Systems
Not a member yet
393 research outputs found
Sort by
Exploring future C++ features within a geometric modeling context
Get PDFThe development of the C++ programming language and its standard library has undergone a renaissance since the introduction of the C++11 standard, making the language more relevant than ever, through modern features, simplification and expansion of the standard library. Comparing past and future feature sets (C++17, C++20, ...) similar to comparing different programming languages. In this article we look at how new and upcoming features of the language can be utilized to ease the development of domain specific application areas through features such as generic programming, compile-time polymorphism and type-safety. We provide representative examples by application to differential geometry by modeling hierarchical structure for parametric object evaluation
A faster all parallel Mergesort algorithm for multicore processors
Get PDFThe problem addressed in this paper is that we want to sort an integer array a[] of length n in parallel on a multi core machine with p cores using mergesort. Amdahl’s law tells us that the inherent sequential part of any algorithm will in the end dominate and limit the speedup we get from parallelisation. This paper introduces ParaMerge, an all parallel mergesort algorithm for use on an ordinary shared memory multi core machine that has just a few simple statements in its sequential part. The new algorithm is all parallel in the sense that by recursive decent it is two parallel in the top node, four parallel on the next level in the recursion, then eight parallel until we at least have started one thread for all the p cores. After parallelization, each thread then uses sequential recursion mergesort with a variant of insertion sort for sorting short subsections at the end. ParaMerge can be seen as an improvement over traditional parallelization of the mergesort algorithm where one follows the sequential algorithm and substitute recursive calls with the creation of parallel threads in the top of the recursion tree. This traditional parallel mergesort finally does a sequential merging of the two sorted halves of a[]. First at the next level it goes two-parallel, then four parallel on the next level, and so on. After parallelization my implementation of this traditional algorithm also use the same sequential mergesort and insertion sort algorithm as the ParaMerge algorithm in each thread. There are two main improvements in Paramerge: First the observation that merging can both be done from the start left to right picking the smallest elements of the two sections to be merged, and at the same time from the end of the same sections from right to left picking the largest elements. The second improvement is that the contract between a node and its two sub-nodes is changed. In a traditional parallelization a node is given a section of a[], sort this by merging two sorted halves it recursively receives from its own two sub nodes and returns its to its mother node. In Paramerge the two sub nodes each receive a full sorting from its two own sub nodes of the section itself got from its mother node (so this problem is already solved). Every node has a twin node. In parallel these two twin nodes then merge their two sorted sections, one from left and the other from right as described above. The two twin sub nodes have then sorted the whole section given to their common mother node. This goes also for the top node. We have thus raised the level of parallelization by a factor of two at each level of the top of the recursion tree. The ParaMerge algorithm also contains other improvements, such as a controlled sorting back and forth between a[] and a scratch area b[] of the same size such that the sorted result always ends up in a[] without any copy, and a special insertion sort that is central for achieving this copy-free feature. ParaMerge is compared with other published algorithms, and in only one case is one of the ‘new’ features in Paramerge found. This other algorithm is described and compared in some detail.Finally, ParaMerge is empirically compared with three other algorithms sorting arrays of length n =10,20,…,50 m, and ..1000m when p=32. demonstrating that it is significantly faster than two other merge algorithms, the sequential and the traditional parallel algorithm, and Arrays.sort(), a sequential Quicksort algorithm from the Java library
Stream-based dynamic data race detection
Get PDFDetecting data races in modern code executing on multicore processors is challenging. Instrumentation-based techniques for race detection not only have a high performance impact, but also are not likely to be certified for safety-critical systems. This paper presents a data race detector based on the well-known lockset algorithm in the runtime verification language TeSSLa, which is a stream-based specification using dynamic data structures to record lock operations and memory accesses. Such a specification can then be instantiated with particular parameters to make it suitable for the more limited planned monitoring using field- programmable gate arrays
The Pocket Reasoner -- Automatic Reasoning on Small Devices
Get PDFAutomated reasoning in classical first-order logic is a core research field in Artificial Intelligence. Most of the fully automated reasoning tools are large and complex systems implementing proof search methods that have significant memory requirements. This paper presents an automated reasoning tool implemented on an iPod Nano. It is based on leanCoP, a very compact Prolog implementation of the connection calculus, which operates on the structure of the given formula without generating new subformula instances. Hence, the memory requirements are significantly lower, allowing leanCoP to run on devices with only little (random-access) memory. The paper presents details of the proof search calculus, its implementation, and a practical evaluation of the presented reasoning tool
How companies find and evaluate graduate computer programmers
Get PDFHow do companies of today hire computer programmers? Within existing research we find that social media now plays an important part when companies are searching for and evaluating talent. We also find multiple studies who describe technical evaluation tools that may be necessary in a screening process when many candidates are fighting for the same position.Through semi-structured interviews with 10 companies, we find that these companies use multiple channels when they search for candidates. We propose a model with four steps to explain the recruitment process: Discovery, Contact, Screening and Selection. Online and physical presence is important for our companies fighting for the attention of talented students. They arrange hackathons and competitions to get to observe candidates, and not just their programming skills. They will attend different student events within university campus, and they will give guest lectures.The ideal situation for a company is when a talented student seeks out the company out of her own interest. The candidate is especially interesting if she may document her knowledge and skill-set through an online presence. If so, a candidate’s code will be a natural topic within an interview. The interview is still an important part of the recruitment process. To place a job advertisement is still common, but it creates a lot of overhead. We find that the companies are reluctant to place themselves in a situation where screening tools become necessary
En eksempel-studie av automatisk tilbakemelding for programmeringsfag i høyere utdanning.
Get PDFDenne studien er gjennomført i forbindelse med eksamen i et førsteårs programmeringsemne ved et universitet. Vi har undersøkt hvordan vi ved bruk av et egenutviklet verktøy for sensurering som består av kvantitativ vekting og som samtidig genererer kvalitative tilbakemeldinger til studentene forbedrer kvaliteten på sensur og på eksamensoppgavene, og ikke minst støtter studentenes videre læring. Gjennom analyse av kvantitative data generert av systemet, samt kvalitative data fra involverte parter fremkommer tydelig forbedringer i validitet og reliabilitet i sensur, samt positive erfaringer fra sensorer og faglærere og ikke minst fra studentene som opplever at det å få tilbakemelding på eksamen bidrar til deres læring og utvikling. Vi vil i denne artikkelen beskrive prosessen med å utviklingen dette systemet for sensur og automatisk tilbakemelding, og presentere resultatene sett fra faglærere, sensorenes og studentenes perspektiv
Energiautomater, energifunktioner og Kleene-algebra
Get PDFForfatterne til denne artikel har, sammen med mange gode kolleger, i en del år arbejdet med såkaldte energiproblemer. Disse handler om, at man i en formel model ønsker at bestemme, om der findes en endelig eller uendelig eksekvering under hvilken en given energivariabel aldrig bliver negativ. Den formelle model kan være en vægtet tidsautomat, en endelig automat som er annoteret med energifunktioner eller lignende. Fælles for alle disse modeller er, at det har vist sig ualmindeligt svært at løse sådanne energiproblemer og at teknikker fra Kleene-algebra har været en stor hjælp.
Formålet med denne artikel er at give et overblik over nylig forskning i energiproblemer (for første gang på dansk) samt at udvide anvendelsen af Kleene-algebra i et forsøg på at lukke et åbent problem fra artiklen som startede hele dette område. 
Mapping Data to Ontologies with Exceptions Using Answer Set Programming
Get PDFIn ontology-based data access (OBDA), databases are connected to an ontology via mappings from queries over the database to queries over the ontology. In this paper, we define an ASP-based semantics for mappings from relational databases to first-order ontologies, augmented with queries over the ontology in the mapping rule bodies. The resulting formalism can be described as ”ASP modulo theories”, and can be used to express constraints and exceptions in OBDA systems, as well as being a powerful mechanism for succinctly representing OBDA mappings. Furthermore, we show that brave reasoning in this setting has either the same data complexity as ASP, or is at least as hard as the complexity of checking entailment for the ontology queries. Moreover, despite the interaction of ASP rules and the ontology, most properties of ASP are preserved. Finally, we show that for ontologies with UCQ-rewritable queries there exists a natural reduction from our framework to ASP with existential variables
A dynamically changing spline curve for the motion of a game character
Get PDFIn computer games a frequent gameplay mode consists of a non-player character (NPC) which patrols around to defend certain items. The player tries to collect these items for her inventory. The NPC’s role is to make this challenging (in an entertaining way) for the player. The NPC’s patrol path is often implemented by using the A* algorithm. In this paper we present an algorithm which uses B-splines and basic learning concepts to construct the NPC’s path, and its motion and behavior in general. We look at some learning strategies for the NPC and use gamedesign concepts to construct the spline curves. The NPC’s path will be a dynamically changing spline curve based on gameplay principles and the NPC’s knowledge