I am a novice to parallel computing. I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example, a multicore workstation) that will implement the parallel version of the GA. But the simulator should run on a serial processor. I know the basics of GAs and I know how to design a GA algorithm to solve the TSP. I thought that this could be an example of an "embarassingly parallel" problem in the sense that I could assign each processor a fixed number of chromosomes (i. e, potential solutions, with solution meaning a given sequence of cities to be visited as specified by the chromosome) with the task of calculating the objective function for each of the assigned chromosomes. In this case, the objective function for a given chromosome is the inverse of the total distance described by that chromosome. The task of performing crossover and mutation would be carried out by a master processor. If this is a valid or reasonable way of parallelizing the problem, then there's no need for inter-processor communication during the objective function evaluation step and I can hardly see this as a truly parallel problem. Since minimum communication is needed, wouldn't the speed scale with the number of processors? What would we learn from such a simulation that we don't already know? I'll be grateful for any thoughtful answers.
-
4$\begingroup$ There is no speedup if you emulate a parallel computer with a serial one of course. What's the end goal? $\endgroup$– haroldApr 23, 2016 at 19:28
-
$\begingroup$ Speedup is not the end goal here. It is simply to simulate a parallel computing platform on a serial computer. Are there free, easy-to-use simulators/emulators of a parallel computer that let you run a parallel program on a variable number of processors? $\endgroup$– user6004863Apr 24, 2016 at 0:11
-
5$\begingroup$ Just run the parallel program(s) on a system with one processor. The operating system will take care of the rest. $\endgroup$– adrianNAug 18, 2016 at 10:10
-
1$\begingroup$ What are your goals? You can learn things from any product you create, but unless we understand what kind of things you're trying to learn, it's hard to create an answer. It sounds like you're saying "This is a problem which is uninteresting from a parallel computing perspective, but can it be interesting to make a serial version of this uninteresting parallel computing problem?" $\endgroup$– Cort AmmonAug 18, 2016 at 23:24
-
$\begingroup$ I'm not sure I understand the problem, but most APIs / frameworks that allow you to harness multiple cores don't care how many you actually have. For example, assigning a task queue to a thread pool ( en.wikipedia.org/wiki/Thread_pool ) it doesn't matter how many threads you have (and the threads be run by multiple processors) More generally, you could write an algorithm in terms of some "Parallelizable" interface with functions like "map", etc, and those functions could have sequential or parallel implementations. $\endgroup$– Kurt MuellerNov 16, 2016 at 15:22
3 Answers
The Traveling Salesman Problem (TSP) is a classic problem because it's hard to deterministically solve in a decent time frame, classified as NP-hard. Genetic algorithms can get a good solution more quickly than NP-hard time, but there's no guarantee that you'll find an actual optimal solution. This can be a good trade-off if you're programming, say, a driving-direction app, but it doesn't get around the NP-hard issue since it doesn't reliably solve the actual NP-hard problem.
Note that genetic algorithms are stochastic (probabilistic). It's entirely possible that you could guess the exact best solution on the first go, or that you'd never guess it after a billion years.
I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example, a multicore workstation) that will implement the parallel version of the GA. But the simulator should run on a serial processor.
As others have said, this will cause your program to run slower than if you hadn't split it up. Parallel solution techniques are inefficient compared to single-threaded solution techniques; the only reason that we use them is to leverage additional processors. If you don't actually take advantage of additional processors, you pay the cost for it without enjoying the benefit.
That said, almost all modern computers have multiple cores, even cell phones and tablets. In the paragraph above, "processor" refers to a processing unit, which single CPU's have multiple instances of. Your computer probably has at least 2 if it's a laptop or 4 if it's a desktop.
Also, note that processors often claim to have twice as many "logical cores". When doing numerical problems, you mostly just care about physical cores; ignore the additional logical cores. With Intel processors, this means ignore Hyper-Threading. With AMD processors, this often means dividing their claimed count by two, since I think that they share floating-point units (FPU) between cores. Those extra logical cores are useful in common computer tasks where there are thread waits and such, but they're usually harmful in scientific computing.
Since minimum communication is needed, wouldn't the speed scale with the number of processors?
Ideally, if you get 100% parallelization efficiency, total speed is equal to the speed of each of the individual processors working individually, combined. Lots of things detract from that ideal, including communication time.
As much as possible, you want to split the problem up into large chunks that a processor can focus on, then combine those chunks at the end, or at least infrequently.
Too much communication will actually make a bunch of processors working together slower than a single one working alone. For example, consider
return a + b + c + d; // Single-threaded calculation
If you split this up into
half1 = worker1.Add(a, b);
half2 = worker2.Add(c, d);
return half1 + half2;
, your program will run much slower than in the first case, despite using multiple cores. The problem is even calling other threads costs far more than simply adding the numbers together, so you've slowed the program down by a huge factor as soon as you do the first worker call.
The trick to remember is that you want to call workers only when you have a lot of work for them to do while the current thread does a lot of work itself. If that doesn't hold, then it's more efficient to just do the work in the current thread.
What would we learn from such a simulation that we don't already know?
Nothing, really. This is a common homework problem in many college classes on optimization, so it's been done hundreds of thousands of times before. I'm assuming that this is part of one of your homework problem sets.
Conclusion
If you're in college, you may have access to a good version of Visual Studio through Microsoft Imagine (previously called DreamSpark). If not, you can download Visual Studio 2015 Community (noting that 2017's in RC right now).
If you use C# in Visual Studio, it should be pretty straightforward to create your parallel genetic algorithm optimizer for the traveling salesman problem. Since your PC's probably already multi-core, you can take advantage of the speed up from it. But, even if it's not multi-core, you can still do multi-threaded runs, and the OS will interleave the threads to simulate a multi-core process.
I'll have to make some assumptions here. It seems you have a problem where some amount of work X could be distributed on practically any number of processors, while some other work Y needs to run on one processor only. And you have a single processor and want information about the behavior on n processors.
You don't really have to simulate a system with n processors. And if you could, the thing that you cannot simulate is the time behaviour. But all you really have to do is measure the time that each task takes, figure out dependencies (where one task cannot continue running until another task has finished), and you should be able to figure out all you want.
At the following paper [1] they are talking about some cloud simulators, and comparing them with a Raspberry Pi cluster. Basically they are saying that a Raspberry Pi cluster is the cheapest way to have a system with more than 1 CPU. They also saying that cloud simulators are not reflecting to the real network traffic.
So, regarding your question, even if you have a simulator you will not even get close to a cluster machine.
I would suggest you at first, to try threaded parallelism, and if you believe that is worth it, you can buy time at a bigger machine, and work with process parallelism. You can also try process parallelism on multi-core CPUs and then move to a bigger machine.
[1] Fung P.T., White D.R., Jouet S., Singer J., Pezaros D.P., "The Glasgow Raspberry Pi Cloud: A Scale Model for Cloud Computing Infrastructures," icdcsw, pp.108-112, 2013 IEEE 33rd International Conference on Distributed Computing Systems Workshops (ICDCSW), 2013
PS: Can you post the algorithm your going to use?
-
1
-
$\begingroup$ -1. This is very bad advice because almost all computers today, including cell phones, have multi-core processors. It'd be surprising if the OP's computer isn't multi-core. $\endgroup$– NatJan 15, 2017 at 17:08
-
$\begingroup$ Also, I'd add that desktop CPU's tend to be much faster than Raspberry Pi's. Unless you bought lots of them, a desktop-based emulator should be faster, not to mention a lot easier to work with, plus it wouldn't cost all that money and time to assemble the cluster. Don't get me wrong, Pi clusters are neat, but they're not practical for the OP's interest here. $\endgroup$– NatJan 15, 2017 at 17:17