Changes

Jump to: navigation, search

GPU621/Threadless Horsemen

7,671 bytes added, 18:09, 25 November 2018
→‎Comparing Multi-threading in Julia vs OpenMP
== Group Members ==
 
# [mailto:tsarkar3@myseneca.ca Tanvir Sarkar]
# [mailto:nmmisener@myseneca.ca Nathan Misener]
== Introduction: The Julia Programming Language ==
 === Bit of History === * It's a relatively new language and runtime (started in 2009, launched in 2012).* The 1.0 release happened this August (https://julialang.org/blog/2018/08/one-point-zero)* It's very ambitious in the sense that it aims to be very good in several areas. * It was originally thought up by Stefan Karpinski, a CS grad student working on simulating wireless networks<blockquote>" STEFAN KARPINSKI WAS building a software tool that could simulate the behavior of wireless networks, and his code was a complete mess. But it wasn't his fault....He knew how to build software. The problem was that in order to build his network simulation tool, he needed four different programming languages. No single language was suited to the task at hand, but using four languages complicated everything from writing the code to debugging it and patching it....Today's languages were each designed with different goals in mind. Matlab was built for matrix calculations, and it's great at linear algebra. The R language is meant for statistics. Ruby and Python are good general purpose languages, beloved by web developers because they make coding faster and easier. But they don't run as quickly as languages like C and Java. What we need, Karpinski realized after struggling to build his network simulation tool, is a single language that does everything well."https://www.wired.com/2014/02/julia/</blockquote> More info:Developers' blog post on why they created Julia:https://julialang.org/blog/2012/02/why-we-created-julia '''Takeaway''' * MATLAB is often used for scientific matrix calculations and linear algebra * R is used for statistical computing* alternative to matlabPython is used for data science, scripting, web development* faster They might provide great libraries and developer efficiency due to language design, but they're slower than C. Julia has syntax which resembles python, not and is JIT compiled to native machine code thanks to LLVM (Low-level Virtual Machine).It aims to provide great developer efficiency as well as fast cexecution times.Amongst the Julia community, has the language is sometimes referred to as a potential MATLAB killer. It's open source, and the programs execute faster while keeping syntax simple. '''Use Cases''' Various organizations have used Julia in their projects, in a repl variety of fields (Machine Leaning, Bioinformatics, Astronomy, Insurance, Energy, Robtics, etc). [[File:Julia_case_studies.png]] Small Excerpt from Racefox (digital sports coaching company): <blockquote>"Racefox’s classification and motion analysis algorithms were first implemented in C++ to ensure fast execution. Initially, the team planned to send raw accelerometer data from the mobile device to the cloud for quick editprocessing....Modifying the existing C++ code was proving too slow owing to the brittleness of the language, verbosity, and the need to go through lengthy modify-compile-run debug cycles. Racefox’s initial attempt to reimplement their algorithms in Matlab did not work very well. It involved a great deal of signal processing with for-loops and conditionals, something that Matlab was particularly bad at. The whole modify-run-analyze cycle was incredibly slow on Matlab, limiting the scope of experimentation....In about a week, they had a Julia implementation up and running that was orders of magnitude faster than their Matlab implementation. This was back in the Julia 0.2 days. Even as a young language, Julia was proving indispensable. Racefox was able to (very happily) abandon their C++ implementation and focus on one code base for both experimentation and production."https://juliacomputing.com/case-studies/racefox.html</blockquote> More Use Cases:https://juliacomputing.com/case-studies/
== Julia's Forms of Parallelism ==
* multi=== Multi-threading === * Experimental in Julia* Implements the fork join pattern (our focuswe've done it many times now)* multiWe focused on this in our quantitative testing, since at the time of writing code, we only had experience with OpenMP [[File:Omp_fork_join.png]] === Multi-core Or Distributed Processing === <blockquote>"Most modern computers possess more than one CPU, and several computers can be combined together in a cluster....Julia provides a multiprocessing environment based on message passing to allow programs to run on multiple processes in separate memory domains at once."https://docs.julialang.org/en/v1/manual/parallel-computing/</ distributed processing blockquote> * Implements message passing* Similar to MPI, but has some key differences '''Message passing in Julia is one sided (programmer only explicitly manages one process in a two-process op).''' <blockquote>"Distributed programming in Julia is built on two primitives: remote references and remote calls. A remote reference is an object that can be used from any process to refer to an object stored on a particular process. A remote call is a request by one process to call a certain function on certain arguments on another (like mpipossibly the same) process."https://docs.julialang.org/en/v1/manual/parallel-computing/</blockquote> '''Unlike sending and receiving messages using MPI, in Julia you would invoke a remote call, which is async.''' * you pass in the function, id of process to execute it, and args for the function* a Future is returned, which is a remote reference to the memory location associated with the process executing the function* you can call fetch on the Future to get the result [[File:Julia_remote_call.png]] https://www.youtube.com/watch?v=RlogUNQTf-M (Introduction to Julia and its Parallel Implmentation, 2:00) === Coroutines (Green Threads) === '''Background:''' * OS processes are instances of a program being executed, and each one has its own address space* OS Threads are essentially lightweight processes, which share a process' address but maintain their own stack (processes can have many threads)* Fibers are a newer concept, and they're essentially lightweight threads which have their own stacks and start/yield (stop) during thread execution (threads can have many fibers)* Coroutines and fibers are functionally equivalent [[File:Fibers_in_thread.png]] <blockquote>"Fibers implement user space co-operative multitasking, rather than kernel level pre-emptive one. Thus, a fiber can not be forcefully pre-empted by the OS kernel...Fibers do have their own stacks, but the fiber switching is done in user space by the execution environment, not the OS kernel generic scheduler....Fibers are a concurrency concept, but are not truly parallel. Typically, each fiber has a parent thread, just as each thread belongs to a process. Multiple fibers from the same thread can not run simultaneously. In other words, multiple execution paths can coexists in the form of fibers (i.e. concurrency) but they can not actually run at the same time (parallelism)....Using a fiber library can be cumbersome, and thus some programming languages introduce coroutines. The two concepts are functionally equivalent. However, coroutines are implemented with specific syntax on the programming language level."https://nikgrozev.com/2015/07/14/overview-of-modern-concurrency-and-parallelism-concepts/</ green threadsblockquote> 
== OpenMP vs Julia Code ==
 
=== For Multi-threading ===
 
* Need to install Julia runtime, and set JULIA_NUM_THREADS env var just like you set OMP_NUM_THREADS
* Julia code is more concise than C/C++ (also simpler to initialize arrays, don't need to manage memory)
* Note that OpenMp code uses loop interchange (ikj) and Julia doesn't (ijk), which will be explained in the next section
== OpenMP vs Julia Results ==
 
* add graphs
* recap loop interchange benefits for openmp (locality of reference)
* discuss julia storing arrays as column major, loop interchange was worse for julia
* discuss different levels of optimization
 
== Conclusion ==
 * summary Julia's a very a new language compared to C++, MATLAB, Python* Mostly used in scientific computing, but designed to be good at many things* JIT compiled to native code thanks to LLVM, faster than interpreted languages like Python, slower than compile-ahead-of everything-time languages like C++* Although slower than C++, implements simpler syntax (looks similar to Python)* The default compiler takes care of optimization tasks for you. Don't need to worry about locality of reference (loop interchange) or vectorization* Multi-threading is still experimental, and it's recommended to use distributed processing or coroutines (green threads) for parallelism
Tsarkarcd
93
edits
Retrieved from "https://wiki.cdot.senecapolytechnic.ca/wiki/Special:MobileDiff/136155"

Navigation menu