|
Sidan är under uppdatering. Essay Project ProposalsThemes: Security, protocols and systems, programming languages, algorithms and complexity SecurityTitle: Fuzzing Theme: Security Subject: Fuzzing is a technique for software vulnerability testing. The idea is to provide applications with ranges of valid or invalid input and in this way try to cause the application to act in an unexpected or faulty manner. An efficient fuzzer will give good coverage at small cost, i.e. it will generate as many and as diverse faults as possible while using as few and as small tests as possible. The inputs may be randomly generated, or they may be guided by knowledge of the protocols and applications, and by heuristics, i.e. test generation strategies that are known to often give good results for the type of application under stress. Often, some form of grammar is used to generate the well-formed inputs and otherwise guide the test generation process. Examples of fuzzers suitable for this project:
CAVEAT: *Never* attempt to perform vulnerability or penetration testing without proper authorization! Possible essay projects:
References:
Title: WebGoat, WebGoat Lesson Development Theme: Security Subject: WebGoat is a J2EE web application developed by OWASP, the Open Web Application Security Project, to teach web application security. The intention is to provide a safe but realistic teaching environment for students to experiment with and learn various types of attacks on web applications. Currently, WebGoat has lessons for many common attack types, such as SQL injection attack, cross-site scripting (xss) attacks, and much else. Possible essay projects:
References:
Supervisor: Mads Dam Title: Security Monitoring Theme: Security Subject: Security monitoring is a technique used to enforce security policies, for instance for access control. A very general and flexible approach to security monitoring uses automata to represent security policies. For instance, a security automaton with two states *unchecked* and *checked* can be used to define the policy that boarding of an aircraft should be allowed only after checkin has been properly completed. In a recently completed EU project S3MS (www.s3ms.org) we have explored the use of security automata and automata inlining for Java and J2ME and a prototype inliner has been developed. A lot of open ends are left, however, which may be suitable for small student projects. Possible essay projects:
References:
Supervisor: Mads Dam Title: Secure Multiparty Computation Made Simple Theme: Security Subject: Secure multiparty computation (SMC) is the problem of securely distributing a computation among several, mutually distrusting parties, so that the computation nonetheless can be completed with strong guarantees that secrets are not revealed, and that, if one of the parties try to cheat by not completing a computation step properly, that party will be discovered. General results by Ben-Or, Goldreich, Widgerson and others show that any computation can be secretly shared but the contructions are complex and not very efficient. A recent paper by Maurer [Maurer-06] gives a particularly simple construction which is nonetheless powerful and may be suitable for essay work for mathematically inclined students. Possible essay projects:
References:
Supervisor: Mads Dam Title: Secure execution of python Theme: Security Subject: Executing code in a controlled
environment, a Python is becoming an increasingly popular language. Investigate various solutions to safe execution of python code. Test some approaches and make a recommendation for how python programs might be sandboxed if language support for python were to be added to Kattis. References:
Supervisor: Mikael Goldmann Title: Hashing schemes Theme: Algorithms and data structures Subject: Implementations of dictionary data structures often rely on binary trees or hash tables. Hashing requires collision handling for which there are several strategies. The most common variants of are hashing with chaining and open addressing. Both come with an average case constant time lookup but no strong guarantees on worst case performance. Newer schemes such as perfect hashing and cuckoo hashing are aimed at having good worst case performance as well. Study several hashing schemes, including at least one of the two newer ones mentioned above. Devise benchmarks for testing their efficiency under various mixes of dictionary operations apply the benchmarks to dictionary implementations. Find out how dictionaries are supported in some common computer languages, and hence what kind of performance one might expect. References:
Supervisor: Mikael Goldmann Title: Proof of work Theme: Security Subject: One way to try to avoid DOS attacks,
brute force attacks or having someone use a mail server for mass email
(SPAM) is to use a proof of work
protocol. Essentially it involves the server not processing a client
request right away. Instead it sends a Study, present and implement a proof of work protocol. Explain assumptions and examine performance. References:
Supervisor: Mikael Goldmann Title: Secure multipatry computation Theme: Security Subject: In the design of secure cryptographic protocols, one important aspect is to define what it would mean for the protocol to be secure — without a definition of security, it is of course impossible to prove that a protocol is secure. The notion of an ideal functionality can be intuitively described by an example. Consider the following sealed bid auction: There is a trusted person to whom all others can send a bid over a secure channel. Once the auction is over the winner is the one who handed in the highest bid, and that person pays the value of the second highest bid. The trusted person announces the winner and the value of the second highest bid and the bidders do not learn anything else about the other bids. This would be our ideal functionality. Now, let us say that we want to remove the trusted person and instead use cryptography. We then want to prove that the cryptographic protocol behaves the same as the ideal functionality, i.e., that (for all practiacal purposes) the outcome is the same and the information leaked to the participants is the same. Viff is a python framework for implementing secure multiparty computation. Use it to implement some simple examples. Document your examples and the properties of Viff. References: Supervisor: Mikael Goldmann Title: Cognitive authentication schemes Theme: Security Subject: Cognitive authentication schemes are an alternative to password authentication. Passwords have the advantage of being simple to use as they only require you to remember a secret, but they are vulnerable to eavesdropping attacks such as key loggers that might be installed on a computer that you do not yourself control. As an alternative, there are schemes relying on the user to memorize a few images and the system then prompting the user with a set of images, some of which are among the one the user has memorized. A simplified description would be that the system presents the user with a matrix of images and the user responds by telling the system which rows contains images from the user's set. Repeating this a number of times decreases the likelihood that an attacker would guess the correct rows each time. After, say, 10 successful challenges the user is authenticated. Study such a scheme and either implement it and do usability tests or study and implement attacks on such a scheme. The report should describe the studied system, your tests and your findings. References:
Supervisor: Mikael Goldmann Protocols and SystemsTitle: Google Wave Theme: Protocols and systems Subject: Google Wave is both a web application hosted by Google and a protocol for real-time communication and collaboration. Essentially, the wave protocol maintains a distributed tree which may contain text and various media types, and which users grow in collaboration. In real-time operation a wave is a form of chat, except that it offers a very dynamic and flexible form of collaboration. Waves may also be stored and replayed at a later time and be embedded in e.g. a blog. Possible essay projects:
References:
Supervisor: Mads Dam Title: Data Serialization, parsing, deparsing - Protobuf, Thrift, Avro Theme: Protocols and systems Subject: Many applications need to convert structured data to serialized form, for instance for data communication. Serialization tools such as Protobuf, Thrift, or Hadoop Avro take as input a description of a data structure, or data schema. The tools then produce methods to encode to and decode from binary representation, including things like getters and setters to access individual fields. Possible essay projects:
References:
Supervisor: Mads Dam Title: Hadoop Theme: Protocols and systems Subject: Apache Hadoop is a large and complex framework for building large scale, reliable distributed systems including database support for large tables in the style of Google's bigtable, a distributed file system, systems management tools, and an implementation of Google's MapReduce framework for processing large amounts of data in parallel. Each of the Hadoop subprojects easily offers study material for several essay projects, and can cater for both students that are practically and theoretically inclined. Project ideas:
References:
Supervisor: Mads Dam Title: Mechanical Turk Theme: Protocols and systems Subject: Mechanical Turk (or Mturk) is a work infrastructure, provided by Amazon, that allow people to perform quick tasks over the web for a small payment. The tasks (called "HITs", "Human Intelligence Tasks") are typically things that computers do poorly, like tagging pictures or assessing the effectiveness of commercial slogans. The people that perform the tasks (the "Workers"), sign in and choose a HIT they like and are qualified to do. The business that has created the task (the "Requester") checks the quality of the performed work, and pays the helper if the work is well done. Possible essay project:
References:
Supervisor: Johan Boye Programming LanguagesTitle: A Prototype Implementation of Featherweight Java in Prolog Theme: Programming languages Subject: Featherweight Java is a minimal version of Java designed for research into Java like languages. The key features of Featherweight Java - syntax, type system, computation rules - are formalized by simple rules that can be implemented in a logic programming language such as Prolog (or Java, or a functional language of your choice. Prolog is convenient for the purpose, though) without too much effort. One or more projects can be defined focusing on one or more of parsing, type checking, and interpreting (computing). Project ideas:
References:
Supervisor: Mads Dam Title: Software model checking using BLAST or SPIN Theme: Programming languages Subject: Model checking is based on the idea of automatically traversing a program execution graph to determine some desired property such as: Is there a way for program line 47 to be executed? Will execution eventually terminate? Does the equation x = y^2 - tmp always hold? Since these problems are generally undecidable, answers cannot be guaranteed, neither can they be guaranteed to be obtainable in reasonable time. Even so, with good engineering and using suitable abstractions, good results can nonetheless often be obtained. Examples of model checkers are BLAST, for C programs, and SPIN which is mainly applied to communications software or protocol modeling. Project ideas: The goal of an essay project on software model checking would be to learn a model checking tool such as BLAST or SPIN and apply it to a selected application. Many examples exist in the literature which can serve a suitable starting points. It would be possible, for instance, to start from a worked example and augment it step by step by adding some additional features. It is important to keep in mind that complexity often increases very quickly, so by adding features simplifications of the existing code/models will very often be needed. So small increments are highly recommended. References:
Supervisor: Mads Dam Title: Call by contract and SPEC# Theme: Programming languages Subject: In the call-by-contract paradigm, methods, objects, and classes are equipped with contracts - formal assertions - that describe how they are expected to behave. For instance, methods may be equipped with pre- and postconditions to determine properties that should be established upon method entry, resp. exit. Much work has been been done to realize such contract-oriented programming frameworks over the past 10-15 years. A well-known example for Java is the Java Modeling Language, JML, for which a number of prototype tools have been developed. See the reference below. Another example is SPEC# which extends the C# programming language with contracts. A related project is Code Contracts, also at Microsoft Research, which uses Microsoft's common intermediate language format to support contracts in a more language-independent way. Project ideas: Projects can be defined based on one of the JML tools, SPEC#, or Code Contracts. Many other tools with similar functionality exists, including some developed here. A suitable project will be to select one of the above tools and learn it well enough to apply it to a selected application. Given the time available for the work, it is better to start from something modest and add complexity, than the other way around. One possible outcome for the ambitious might be to produce a lab suitable for a future advanced programming languages course. References:
Supervisor: Mads Dam Title: Makumba Theme: Web development frameworks/Programming languages Subject: Makumba is a web development framework for programmers who know HTML and some query language like SQL. A novice programmer can start working with Makumba after a training of 1-2 hours. Makumba renders good scalability for teams and projects: a 10-person team (with membership changing each year) developed an intranet with several thousand features over the course of 8 years. Some of the rules of Makumba applications are written in Java, but the bulk of the application is done in MQL (Makumba's query language, a subset of Hibernate HQL) and HTML. Makumba is available in JSP (Java Server Pages) as a "tag library". Since most aspects of development (viewing data, entering and modifying data, authentication, authorization) can be done in Makumba using queries or query fragments, Makumba is said to be query-centric. Possible essay projects:
References:
Supervisor: Cristian Bogdan Language TechnologyTitle: Linguistic steganography Theme: Language technology Subject: Steganography is the technique of hiding secret messages. For instance, if one writes a message with lemon juice on a piece of paper, the paper looks blank until it is heated, when the message magically re-appears. Another example is the technique (used during the second world war) of shrinking a text to a tiny dot, and then hiding the dot on top of a full stop in an innocuous letter. A recent twist of the same idea is linguistic steganography, where secret machine-readable data is encoded as a seemingly innocuous natural-language text. This can be done either by generating the natural-language text from scratch in such a way that it encodes the secret message, or alternatively by modifying an existing text. In the latter case, the encoding is made by making cleverly substituting sentences, words or characters in the original text. Possible essay project:
References:
Supervisor: Johan Boye Title: Automatic translation Theme: Language technology Subject: Online tools for automatic translation, like Google Translate and BabelFish, are getting increasingly better. But how good are they? And what methods do they use? Possible essay project:
References:
Supervisor: Johan Boye Title: Co-reference resolution experiment Theme: Language technology Subject: Words or expressions in a text that refer to the same object are said to "co-refer". Finding co-referring expressions is an important subproblem in some natural-language applications, such as information retrieval. As an example, consider the following text snippet: "När Babbage övergav sin första maskin tappade staten förtroendet för honom och beslöt att minska förlusterna genom att dra sig ur projektet. De hade redan satsat 17 470 pund, nog med pengar för att bygga ett par slagskepp." (from Simon Singh, "Kodboken", page 86, Norsteds förlag, 2000). In this passage "Babbage" and "honom" are co-referring expressions, as are "staten" and "De". Possible essay project:
References:
Supervisor: Johan Boye Title: Detecting plagiarism Theme: Language technology Subject: Plagiarism is the fraudulent act of copying parts of someone else's text and presenting it as one's own work. Plagiarism in schools and universities is a bigger problem than one might think (e.g. see the statistics presented at http://www.plagiarism.org/). Consequently, there are several tools on the market that attempts to detect plagiarism. The question is how good these tools are. Possible essay projects:
References:
Supervisor: Johan Boye Title: Automatic classification of opinions Theme: Language technology Subject: Many companies worry about their public image. Therefore it is of great interest to be able to automatically sift through blogs and articles and count the number of occurrences where the a certain product is mentioned in a positive way, and compare it to the number of times it is mentioned in a negative way. It order to do this rapidly and to a low cost, it would be preferable to use a simple classification method, provided it gives sufficiently accurate results. One possibility is to use a "bag-of-words" approach, i.e. only take into account which words occur in the text, not their grammatical relations. Possible essay project:
References:
Supervisor: Johan Boye Title: Wizard-of-Oz studies Theme: Language technology Subject: A Wizard-of-Oz study is an experiment where people are asked to communicate with a system which they are led to believe are fully automatic, but is actually operated by a human being. In particular, this methodology has been extensively used when developing natural-language interfaces. Possible essay project:
References:
Supervisor: Johan Boye Artificial IntelligenceTitle: Self-learning game player Theme: Artificial intelligence Subject: Reinforcement learning is a technique of letting computer programs learn what actions to take in various situations simply by trying out (some of) the possible actions and observing the result. Thus, reinforcement learning is "unsupervised" -- the program learns by interacting with the environment and is never explicitly told which action is the best one. A game-playing program might use reinforcement learning to acquire its strategic knowledge. A way of bootstrapping that knowledge is to let the program play against itself. It is an interesting exercise to find out how good a program can become just by using this technique. Possible essay project:
References:
Supervisor: Johan Boye Title: Is artificial intelligence possible? Theme: Artificial intelligence Subject: The question whether or not a machine can be intelligent has been hotly debated since the inception of the term "artificial intelligence" (and indeed well before that). Some of the most outspoken opponents have been the American philosopher John Searle, known for his "Chinese Room" thought experiment, and the British matematician Roger Penrose. Possible essay project:
References:
Supervisor: Johan Boye Algorithms and ProblemsTitle: Multi-skill call centers Theme: Problem solving Subject: Modern call centers often handle a large variety of calls. When a customer calls, he is first asked to give information concerning his reason for calling. This is usually made either via a push-button interface, or an interface that employs automatic speech recognition. Once the type of the call has been identified, the call is routed to a queue serviced by dedicated service agents. On the other hand, many service agents have multiple skills and are capable of handling more than one type of call. Thus, in general the relation between call types and service agents is a many-to-many relation (i.e. calls of a given type can be handled by several different agents, and a given agent can handle serveral different call types). Due to the ever-increasing proliferation of such multi-skill call centers, their organisation and properties has become an active research area. Two of the problems studied by computer scientists and mathematicians is the staffing an routing problems:
Possible essay project:
References:
Supervisor: Johan Boye Title: Page Ranking Algorithms for the Web Theme: Graph Algorithms Subject: The GOOGLE search engine orders the pages found according to their PageRank, described in [1]. For a large graph, the computation of PageRank is a serious undertaking, and efficient algorithms are an active area for research. Project ideas: A survey of methods are given in [3]. The essay shall explain the ideas behind the ranking, its mathematical model of the web, and discuss algorithms to compute the ranking, with [1] and [3] as background. Paper [2] proposes a pre-ordering which is a standard graph algorithm to find strongly connected graphs, which is also used in solving large, sparse linear systems of equations. The essay could review [2] in light of [1] and [3], and/or report on the group’s own experiments carried out with test matrices, see [2]. References: [1] S.Brin, L.Page, R.Motwami, and T.Winograd, "The PageRank citation ranking: Bringing order to the web". Technical report, Computer Science Department, Stanford University, 1998, http://ilpubs.stanford.edu:8090/422/ [2] http://dsp.vscht.cz/konference_matlab/matlab05/prispevky/pultarova/pultarova.pdf [3] A.N. Langville, C.D. Meyer, "A Survey of Eigenvector Methods for Web Information Retrieval", meyer.math.ncsu.edu/Meyer/PS_Files/Survey.pdf Supervisor: Jesper Oppelstrup Computer GraphicsTitel: Partikelsystem, Flockbeteende Tema: Datorgrafik Ämne: Partikelsystem bygger på modellering och visualisering genom att användning av ett större eller mindre antal partiklar som kan ge bilder av t.ex. fyrverkerier, rök, vattenkaskader etc. Tekniken kan också användas för att modellera flockbeteenden hos t.ex. fåglar som tilldelas vissa egenskaper för att hålla ihop, undvika kollisioner etc. Möjliga kandidatprojekt:
Referenser:
Handledare: Lars Kjelldahl Titel: Visualisering av hår Tema: Datorgrafik Att visualisera hår är en utmaning för den som arbetar med datorgrafik. Bakgrunden är att det normalt är många hårstrån – huvudet på en människa har kanske 100 000 hårstrån. Hår är normalt dessutom delvis transparent och vidare kan man vara intresserad av att skapa rörliga sekvenser med hår (animering) och då blir det ännu fler problem att hantera. Möjliga kandidatprojekt:
Referenser:
Handledare: Lars Kjelldahl Titel: Borttagning av skymda ytor Tema: Datorgrafik Ämne: Att ta bort skymda ytor är ett klassiskt problem inom datorgrafik. Problemet är alltså att man har en geometrisk modell av 3D-objekt, men ingen information om vad som är synligt när man betraktar objekten från en viss punkt. Vid utritningen av objekten på skärmen måste man ta reda på vad som syns och ska ritas ut och vad som inte syns och alltså inte ska ritas ut. Möjliga kandidatprojekt:
Referenser: Handledare: Lars Kjelldahl Titel: Grafik med begränsade resurser Tema: Datorgrafik Ämne: Mycket dagens utveckling går mot bärbar utrustning, bl.a. i form av mobiltelefoner. Grafik blir allt vanligare och självklart men de bärbara utrustningarna innebär vissa problem med små skärmar, begränsad minnes- och processorkapacitet, batterikapacitet mm. I framtiden kan vissa av dessa problem minskas eller elimineras, men t.ex. den begränsade skärmstorleken är svårare. Möjliga kandidatprojekt:
Referenser: Handledare: Lars Kjelldahl Titel: Multidimensionell visualisering Tema: Datorgrafik Ämne: Vår vanliga värld är tredimensionell vilket vi använder när 3D-data ska presenteras. Det blir svårare när data har flera dimensioner. Man kan t.ex. använda färg för att ange ytterligare en dimension. Det här är en del av området informationsvisualisering och där arbetar man med presentationsformer som parallella koordinater, punktdiagram (scatter plots), mm Möjliga kandidatprojekt:
Referenser:
Handledare: Lars Kjelldahl Titel: Perceptuella aspekter på datorgrafik och visualisering Tema: Datorgrafik Ämne: Perception spelar roll för vad man ska visualisera i samband med datorgrafik. En vanligt förekommande standardteknik är att rita objekt på långt avstånd med lägre upplösning. Den tekniken kallas för ”level of detail” (LOD). Möjliga kandidatprojekt:
Referenser:
Handledare: Lars Kjelldahl Titel: Textur och ytdetaljer Tema: Datorgrafik Ämne: Normalt när man ritar ut datorgrafikbilder gör man geometriska modeller av de objekt som ska ritas ut. När man har mycket detaljer som t.ex. på en tegelvägg blir det praktiskt svårt (tidsödande) att göra modeller av alla detaljer. Då använder man i stället en slags tapet (textur) som man klistrar på den yta där detaljerna ska vara. Tekniken kallas för texture mapping och finns i olika varianter förutom vanlig standard texture mapping, finns bump mapping, environment mapping mm. Möjliga kandidatprojekt:
Referenser:
Handledare: Lars Kjelldahl Semantic WebTitle: Nepomuk Theme: Semantic Technologies / Collaboration Technology Subject: Nepomuk is the "social semantic desktop" and stems from an European project which put together state-of-the-art semantic technologies "to develop a comprehensive solution for extending the personal desktop into a collaboration environment which supports both the personal information management and the sharing and exchange across social and organizational relations". Nepomuk produced software (of different characters) for two platforms, the Java platform (an Eclipse application called PSEW) and Linux (the Nepomuk components are distributed with KDE). Possible essay projects:
References:
Supervisor: Cristian Bogdan Title: Itsme Theme: Semantic Technologies / Collaboration Technology Subject: Itsme is aiming to find new personal computing metaphors (based on Stories and Venues) as the desktop is considered unsuitable for today's personal computing. In the process, itsme developed very interesting technologies, partly based on Nepomuk and partly developed in-house. The back-end runs on Linux. The technology can be currently tried out via an emulator. Possible essay projects:
References:
Supervisor: Cristian Bogdan Title: Aether Theme:Semantic Technologies / Collaboration Technology Subject: Awareness in computer supported collaborative work (CSCW) is defined as "understanding the activity of others in the context of one's own activity". The Aether engine attempts to provide awareness between users of digital objects interlinked in a "semantic network". One core idea of Aether is that information a user action "percolates" through the semantic network until i reaches users that are interested in the respective action. Percolation is a computationally intensive process. Although Aether was defined in 1997, the compuational challenges for its implementation led to the first implementation in a realistic usage environment to only come in 2008. The current Aether implementation site is a collaborative Interactive Development Environment called Parade with 20 users working with copies of an intranet containing about 3000 files each (therefore the semantic network size is over 60000). To process such large amounts of data for percolation, the implementation uses a relational database. The implementation also aims to explain to the user how percolation took place, for users to understand why they are notified of certain actions. Possible essay projects:
References:
Supervisor: Cristian Bogdan Software ToolsTitle: Software Performance Measurement / Improvement by SlowSpotter Theme: Software tools Subject: Performance monitoring is an issue for through-put bound applications and becomes ever more important with distributed computing and more complex computer architecures. Efficient use of the memory hierarchy is the key to efficient execution. But the road is long between the lines in your C++ code and the machine cycles. How is it possible to relate actual execution traces to the source code, so bottlenecks can be identified and avoided? Project ideas: The essay project shall present experience from learning performance monitoring technology and trying the SlowSpotter tool (free trial version), developed for Solaris and Linux, on a few applications. The tool suggested grew out of research at Uppsala University and SUN. It has a companion ThreadSpotter for multi-threaded codes. If possible, we will make it available to the project. References: [1] http://en.wikipedia.org/wiki/Acumem_SlowSpotter Supervisor: Jesper Oppelstrup SimulationTitle: The TimeWarp “Operating System” Theme: Parallel Discrete Event Simulation Subject: In discrete event simulation, the processes all operate synchronously, but the time for the next event, and which processes to be active at that time, is not known before execution of “this” event. Parallelization by distributing processes over processors is therefore of little use. The TimeWarp idea is to carry on by guesswork, post-fact to check if the sequence was right, and to back up when necessary. A similar approach is taken in compiling optimized serial code for branches such as loop terminations: the data for the most probable set of instructions to be executed next will be pre-fetched. Project ideas: The TimeWarp was promoted by Jefferson & al. in [1] and a number of implementations followed, e.g. the GTW software, [2]. TimeWarp type algorithms have been proposed more recently for continuous system simulation with several time-scales, in particular for computer game physics engines to deal with realistic many soft-body interactions. The essay project shall describe the TimeWarp algorithm, and discuss the pitfalls, with the paper [3] as inspiration, and find material about and discuss also more recent applications such as many-body simulation. References: [1] D.Jefferson & al, "Time Warp Operating System", ACM Symp. on Operating Systems Principles, ACM, Austin TX., (1987), http://doi.acm.org/10.1145/41457.37508 [2] http://www.cc.gatech.edu/computing/pads/teddoc.html [3] D. M. Nicol, X. Liu, "The dark side of risk (what your mother never told you about Time Warp)", ACM SIGSIM Simulation Digest archive 27, 1, (1997), http://doi.acm.org/10.1145/268823.268920 Supervisor: Jesper Oppelstrup Performance optimizationTitle: Automatic tuning of linear algebra routines Theme: Performance optimization Subject: Numerical linear algebra for (non-sparse) matrices and vectors is at the heart of many scientific computations, and development of efficient, reliable software has been intensive since 1970. The Basic Linear Algebra Subprograms, and higher level algorithms collected in e.g. the LAPACK and ScaLAPACK libraries, are now used by all numerical software such as MATLAB. Tuning of the algorithms to the properties of the memory hierarchy is necessary to obtain efficient software. This can be done “manually”, using vendor information, at great cost. For some architectures, like NVIDIA GPU, properties of the hardware are not disclosed. An alternative is an empirical search over the possible variations to find the best parameter settings for a representative set of tasks. Project ideas: The essay shall discuss the empirical approach to library optimization, with reference to [2]. Experiments with the ATLAS software for optimization of LAPACK on Solaris, Linux, or Windows are encouraged. Paper [3] describes manual optimization on NVIDIA GPU, especially the section on how the hardware properties were measured. Paper [1] is an introduction to BLAS, etc. References: [1] L.S.Blackford & al., "An Updated Set of Basic Linear Algebra Subprograms (BLAS)", ACM Transactions on Mathematical Software, 28(2):135-151, June 2002. http://www.cs.utsa.edu/~whaley/papers/blast-toms.pdf [2] R.C.Whaley, A.Petitet and J.Dongarra, "Automated Empirical Optimization of Software and the ATLAS project", Parallel Computing, 27(1-2):3-35, 2001, http://www.cs.utsa.edu/~whaley/papers.html [3] V.Volkov, J.W.Demmel, "Benchmarking GPUs to Tune Dense Linear Algebra", SuperComputing2008, Austin, Texas, IEEE, http://portal.acm.org/citation.cfm?id=1413402 Supervisor: Jesper Oppelstrup
|