# Tag Info

58

The question is: under what constraints? There are certainly problems where, if we ask the question "can we solve this problem on hardware X in the given amount of time", the answer will be no. But this is not a "future-proof" answer: things which in the past could not be done fast enough in a single core probably can be now, and we can't predict what ...

47

If you don't care about the running time, anything you can do on a multi-core machine, you can do on a single-core machine. A multi-core machine is just a way of speeding up some kinds of computations. If you can solve a problem in time $T$ on a multi-core machine with $n$ cores, then you can solve it time $\sim Tn$ (or less look at Amdahl's law) on a ...

17

As other answers have pointed out, a single CPU can always emulate multiple CPUs by slicing time and playing the role of each virtual CPU. This emulation will certainly calculate the correct answers. In the real world, execution time may be important. It could mean the difference between a mediocre frame rate and a stellar visual experience. Or the ...

13

With equation: not really. Superlinear speedup comes from exceeding naively calculated speedup even after taking into account the communication process (which is fading, but still this is the bottleneck). For example, you have serial algorithm that takes $1t$ to execute. You have $1024$ cores, so naive speedup is $1024x$, or it takes $t/1024$, but it ...

12

Obviously, with the various forms of operating systems out there, this process can vary (and in some cases, be completely different) but this outlines a general overview. Step 1: Load the program into memory. This is pretty basic; grab the contents of the program and load it into memory. Depending on how memory is managed by the operating system and the ...

9

The main distinction, as you point out in your question, is whether or not the scheduler will ever preempt a thread. The way a programmer thinks about sharing data structures or about synchronizing between "threads" is very different in preemptive and cooperative systems. In a cooperative system (which goes by many names, cooperative multi-tasking, ...

9

Since the CPU works in fixed clock cycles, nothing is really continuous, only seems so because the discretization is sensitive enough. Suppose your CPU clock rate is $1\text{GHz}=10^9Hz$. If the CPU only devotes one in $t$ clock cycles to processing audio (and utilizes the remaining clock cycles for unrelated tasks) then you have a delay of $\approx t\cdot ... 8 40 years ago, you might have had a computer where the CPU controlled the speaker directly. Those times are over, long ago. You may have a computer with a primitive sound card. Such a sound card will have a buffer for stereo audio samples, that buffer can be filled, the output function will be started, and the sound card starts generating audio from the ... 8 It's much harder to develop really nefarious data races with a single CPU. I mean, sure, you can pull off tearing between words if you interrupt a single CPU, but can you build exotic scenarios where there is no single interleaving of threads which does what you want? Okay, maybe making insidious bugs doesn't count as a valid use of multi-code advancements.... 6 The answer is actually that they could, but there is a desire not to. Fibers are used because they let you control how scheduling occurs. Accordingly, it is much simpler to design some algorithms using fibers because the programmer has say in which fiber is being executed at any one time. However, if you want two fibers to be executed on two different ... 6 The question is mixing up who's in control of the memory and who's in control of the CPU. The wording “running” is imprecise: on a single CPU, a single task is running at any given time in the sense that the processor is executing its instructions; but many tasks are executing in the sense that their state is stored in memory and their execution can resume ... 6 My best guess: a student process is a process run by a student. All users have to log in. The OS may well know various types of users, and may be able to determine from some table that a given user is a student. This can be useful to lower their priority for computer time in a shared machine used mainly for research, or possibly do the opposite during exam ... 6 If you need to observe a process running on a single processing element without disturbing its real-time behavior (or as little as possible), like for benchmarking or activity logging, you'll probably need a separate processing resource. 4 The other answers adhere to the limited view of parallelism as "distributed concurrency". This gives some answers: in a clean model of computation à la Turing, multiple cores do not offer an advantage; the only advantage you may get is efficiency. There is the one thing multiple processing units (PUs) can do that a single one can not, though: execute ... 4 It's great that you're curious. A simplified explanation follows with a few links to delve into: All of the programs running in parallel is actually an illusion that is created by the OS. Even if we have a uniprocessor system, the OS can still achieve the same thing. For multiple programs running on the system, OS creates separate processes. Separate ... 3 Parallelism has costs. The processes have to be scheduled, communicate with each other, manage resources, etc. In return you can do multiple things at the same time. When you have a lot of slow tasks that can be done independently, parallel processing will speed things up a lot. But when you try to parallelize an easy task it might take longer to handle ... 3 Threads On a platform that supports multi-threading the threads run in parallel. That means that multiple threads can run at the same time. This depends on the numbers of cores the CPU makes available. If the programmer insists on running more threads than the CPU has cores then the threads will be time-sliced. How much time each thread gets depends on the ... 2 We can prove that 2-set-consensus among 3 processors (noted (3,2)) cannot be used (together with registers) to solve consensus among 2 processors (noted (2,1)) using the Borowsky-Gafni simulation (BG simulation for short). The BG simulation allows 3 processors using registers only to simulate any algorithm in which 2 processors use registers and (3,2). ... 2 Reading / writing from disk. Reading / waiting for keyboard / mouse input. Reading / waiting for network data. Printing a page. Basically, as the text says, an I/O task is anything which the CPU can't perform on its own, and has to rely on other components. Usually this involves waiting a long time, compared to the CPU speed, so it's better to switch to ... 2 TL;DR The CPU doesn't know anything. The operating system (OS) knows it all. The CPU is rather a stupid machine that activates one instruction at a time, without knowing what that instruction "means" nor to which program it "belongs". To the CPU eyes there is only a single program that runs (maybe, up to interrupts that "jump" to the interrupt service ... 2 Amdahl divided a program in two parts, serial and parallel, and assumed each processor to have same compute ability. This concept has been further refined by Hill and Marty Amdahl's law in multi-core era, in other words it is not necessary that every processor should have same the compute ability and Cassidy Beyond Amdahl's Law: An Objective Function That ... 2 The (non-negligible) cost is the set up of the in-kernel structures to keep track of the new process (setting up page tables and so on). You can easily measure it: Write a small program just like the one you have: #include <unistd.h> /* Define FORK for forking version */ #ifdef FORK #define ROUNDS 10000 #else #define ROUNDS 10000000 #endif int main(... 1 These are two distinct phenomena. Contention refers to the fact that when thread$A$has accessed a resource$B$needs to wait until$A$frees it. Race refers to the fact when both threads$A$and$B\$ want to secure access to a resource. The fastest will secure it and thus lead to contention.

1

Say you have 100 units of work. 30 units are such that only one core can be used while performing that unit of work. 70 units are such that four cores each can perform one unit of work at the same time. That should be enough to give a theoretical answer. But the question is imprecise: can the “serial “ task be in in parallel with three “parallel” tasks? In ...

1

I don't get where the 0.375 came from ? If the CPU utilization is 75%, and it's shared equally between two process, each of them gets 37.5%. What are CPU minutes? A CPU-minute is the amount of work done by one CPU in one minute.

1

For Multiprogramming you may or may not need Preemption. It depends upon the scheduling policy that is being used. For example First in First Out is non preemptive but shortest CPU burst is preemptive. One more thing you are mixing blocking and preemption. When a process needs I/O it uses a system call. This system call results in a trap(software interrupt)....

1

It is possible to extend skip lists with so called "width of the link". For each link it says how many elements are skipped by follow this link. From Wikipedia (section Indexable skiplist): 1 10 o---> o---------------------------------------------------------> o Top level 1 3 2 ...

1

Based on your comment, it sounds like you would also prefer a solution that is not too difficult to understand or implement. I would suggest a persistent binary tree as one possible approach. Take any standard balanced tree data structure (e.g., red-black tree, AVL tree, 2-3 tree, etc.). Annotate each node with the size of the subtree under that node. ...

1

Suppose you are running two concurrent processes (or threads), which both perform intensive disk I/O. Both repeatedly attempt to read/write on some file. Now, the scheduler must decide which requests to handle. The scheduler could serve the first process, then the second on, then the first, etc. in a round-robin fashion. This would guarantee fairness: any ...

1

The early multiprogramming systems ran two or three programs simultaneously in a single computer. They did so by partitioning the memory amongst operating system one user-program another user-program ... The user programs shared a single copy of the operating system, which provided input/output and other services through system calls, which switched the ...

Only top voted, non community-wiki answers of a minimum length are eligible