Computer Science Journal (AGH University of Science and Technology, Krakow)
Not a member yet
476 research outputs found
Sort by
Dynamic Tile Free Scheduling for Code with Acyclic Inter-Tile Dependence Graphs
Get PDFFree scheduling is a task ordering technique under which instructions are executedas soon as their operands become available. Coarsening the grain ofcomputations under the free schedule, by means of using groups of loop neststatement instances (tiles) in place of single statement instances, increases thelocality of data accesses and reduces the number of synchronization events, andas a consequence improves program performance. The paper presents an approachfor code generation allowing for the free schedule for tiles of arbitrarilynested affine loops at run-time. The scope of the applicability of the introducedalgorithms is limited to tiled loop nests whose inter-tile dependence graphs arecycle-free. The approach is based on the Polyhedral Model. Results of experimentswith the PolyBench benchmark suite, demonstrating significant tiledcode speed-up, are discussed
Lower Precision calculation for option pricing
Get PDFThe problem of options pricing is one of the most critical issues and fundamental building blocks in mathematical finance. The research includes deployment of lower precision type in two options pricing algorithms: Black-Scholes and Monte Carlo simulation. We make an assumption that the shorter the number used for calculations is (in bits), the more operations we are able to perform in the same time. The results are examined by a comparison to the outputs of single and double precision types. The major goal of the study is to indicate whether the lower precision types can be used in financial mathematics. The findings indicate that Black-Scholes provided more precise outputs than the basic implementation of Monte Carlo simulation. Modification of the Monte Carlo algorithm is also proposed. The research shows the limitations and opportunities of the lower precision type usage. In order to benefit from the application in terms of the time of calculation improved algorithms can be implemented on GPU or FPGA. We conclude that under particular restrictions the lower precision calculation can be used in mathematical finance.
Multiobjective optimization in the Airport Gate Assignment Problem, exact versus evolutionary multiobjective optimization
No full textIn this paper, we approach the Airport Gate Assignment Problem by Multiobjective Optimization as well as Evolutionary Multi-objective Optimization. We solve a bi-criteria formulation of this problem by the commercial mixedinteger programming solver CPLEX and a dedicated Evolutionary Multiobjective Optimization algorithm. To deal with multiple objectives, we apply a methodology that we developed earlier to capture decision-maker preferences in multi-objective environments. We present the results of numerical tests for these two approaches
Simulation-Based Sailboat Trajectory Optimization using On-Board Heterogeneous Computers
Get PDFA dynamic programming-based algorithm adapted to on-board heterogeneouscomputers for simulation-based trajectory optimization was studied inthe context of high-performance sailing. The algorithm can efficiently utilizeall OpenCL-capable devices, starting the computation (if necessary, in singleprecision)on a GPU and finalizing it (if necessary, in double-precision) withthe use of a CPU. The serial and parallel versions of the algorithm are presentedin detail. Possible extensions of the basic algorithm are also described. Theexperimental results show that contemporary heterogeneous on-board/mobilecomputers can be treated as micro HPC platforms. They offer high performance(the OpenCL-capable GPU was found to accelerate the optimization routine 41fold) while remaining energy and cost efficient. The simulation-based approachhas the potential to give very accurate results, as the mathematical model uponwhich the simulator is based may be as complex as required. The black-box representedperformance measure and the use of OpenCL make the presentedapproach applicable to many trajectory optimization problems
Comparison and Adaptation of Automatic Evaluation Metrics for Quality Assessment of Re-Speaking
Get PDFRe-speaking is a mechanism for obtaining high quality subtitles for use in livebroadcast and other public events. Because it relies on humans performing theactual re-speaking, the task of estimating the quality of the results is non-trivial.Most organisations rely on humans to perform the actual quality assessment,but purely automatic methods have been developed for other similar problems,like Machine Translation. This paper will try to compare several of thesemethods: BLEU, EBLEU, NIST, METEOR, METEOR-PL, TER and RIBES.These will then be matched to the human-derived NER metric, commonly usedin re-speaking
A Blackboard System for Generating Poetry
Get PDFWe present a system to generate poems based on the information extracted from input text such as blog posts. Our design uses the blackboard architecture, in which independent specialized modules cooperate during the generation process by sharing a common workspace known as the blackboard. Each module is responsible for a particular task while generating poetry. Our implementation incorporates modules that retrieve information from the input text, generate new ideas, or select the best partial solutions. These distinct modules (experts) are implemented as diverse computational units that make use of lexical resources, grammar models, sentiment-analyzing tools, and languageprocessing algorithms. A control module is responsible for scheduling actions on the blackboard. We argue that the blackboard architecture is a promising way of simulating creative processes because of its flexibility and compliance with the Global Workspace Theory of mind.The main contribution of this work is the design and prototype implementation of an extensible platform for a poetry-generating system that may be further extended by incorporating new experts as well as some existing poetrygenerating systems as parts of the blackboard architecture. We claim that this design provides a powerful tool for combining many of the existing efforts in the domain of automatic poetry generation
On the Computational Cost and Complexity of Stochastic Inverse Solvers
Get PDFThe goal of this paper is to provide a starting point for investigations into a mainly underdeveloped area of research regarding the computational cost analysis of complex stochastic strategies for solving parametric inverse problems. This area has two main components: solving global optimization problems and solving forward problems (to evaluate the misfit function that we try to minimize). For the first component, we pay particular attention to genetic algorithms with heuristics and to multi-deme algorithms that can be modeled as ergodic Markov chains. We recall a simple method for evaluating the first hitting time for the single-deme algorithm and we extend it to the case of HGS, a multi-deme hierarchic strategy. We focus on the case in which at least the demes in the leaves are well tuned. Finally, we also express the problems of finding local and global optima in terms of a classic complexity theory. We formulate the natural result that finding a local optimum of a function is an NP-complete task, and we argue that finding a global optimum is a much harder, DP-complete, task. Furthermore, we argue that finding all global optima is, possibly, even harder (#P-hard) task. Regarding the second component of solving parametric inverse problems (i.e., regarding the forward problem solvers), we discuss the computational cost of hp-adaptive Finite Element solvers and their rates of convergence with respect to the increasing number of degrees of freedom. The presented results provide a useful taxonomy of problems and methods of studying the computational cost and complexity of various strategies for solving inverse parametric problems. Yet, we stress that our goal was not to deliver detailed evaluations for particular algorithms applied to particular inverse problems, but rather to try to identify possible ways of obtaining such results
Dynamic Turing Machine: model and properties for runtime code changes
Get PDFIn this paper, a dynamic model of computation based on the Universal Turing Machine is proposed. This model is capable of applying runtime code modifications for 3-symbol deterministic Turing Machines at runtime and requires a decomposition of the simulated machine into parts called subtasks. The algorithm for performing runtime changes is considered, and the ability to apply runtime changes is studied through computer simulations. Theoretical properties of the proposed model, including computational power as well as time and space complexity, are studied and proven. Connections between the proposed model and Oracle Machines are discussed. Moreover, a possible method of implementation in real-life systems is proposed
AUTOMATIC PORTAL GENERATION FOR 3D AUDIO - FROM TRIANGLE SOUP TO A PORTAL SYSTEM
Get PDFThe purpose of this paper is to investigate an algorithm for generating an automatic portal system. This has been accomplished based on a given set of triangles. The proposed solution was designed to enhance the performance of a sound beam-tracing engine. This solution can also be used for other areas where portal systems are applicable. The provided technical solution emphasizes the beam tracing engine\u27s requirements. Our approach is based on the work of Haumont et al. (with additional improvements), resulting in improved scene segmentation and lower computational complexity. We examined voxelization techniques and their properties, and have adjusted these to fit the requirements of a beam-tracing engine. As a result of our investigation, a new method for finding portal placement has been developed by adjusting the orientation of the found portals to fit the neighboring scene walls. In addition, we replaced Haumont et al.\u27s prevoxelization step, which is used for erasing geometrical details (for example, thin walls). This was done by smoothing the distance field that, in effect, eliminated incorrectly positioned portals. The results of our work remove the requirement for walls that separate rooms to have a particular thickness. We also describe a method for building a structure that accelerates real-time queries for determining the area where a given point is located. All of the presented techniques allow for the use of larger sized voxels, which increases performance and reduces memory requirements (not only during the preprocessing phase but also during real-time usage). The proposed solutions were tested using scenarios with scenes of varying complexity
REALIZATION OF A SYSTEM OF EFFICIENT QUERYING OF HIERARCHICAL DATA TRANSFORMED INTO A QUASI-RELATIONAL MODEL
Get PDFExtensible Markup Language was mainly designed to easily represent documents; however, it has evolved and is now widely used for the representation of arbitrary data structures. There are many Application Programming Interfaces (APIs) to aid software developers with processing XML data. There are also many languages for querying and transforming XML, such as XPath or XQuery, which are widely used in this field. However, because of the great flexibility of XML documents, there are no unified data storing and processing standards, tools, or systems.On the other hand, a relational model is still the most-commonly and widely used standard for storing and querying data. Many Database Management Systems consist of components for loading and transforming hierarchical data. DB2 pureXML or Oracle SQLX are some of the most-recognized examples. Unfortunately, all of them require knowledge of additional tools, standards, and languages dedicated to accessing hierarchical data (for example, XPath or XQuery). Transforming XML documents into a (quasi)relational model and then querying (transformed) documents with SQL or SQL–like queries would significantly simplify the development of data-oriented systems and applications.In this paper, an implementation of the SQLxD query system is proposed. The XML documents are converted into a quasi-relational model (preserving their hierarchical structure), and the SQL–like language based on SQL-92 allows for efficient data querying