The Big Programming Thread - Page 822

Can you think of other ways to do it? The only way I could think of was basically just versions of DFS that involved backtracking based on checking a list to see if combinations had been completed already but clearly that would be insanely inefficient.

Like, someone highly upvoted on stackexchange said this (it's for string permutations but I imagine the logic is the same yes?)

On December 29 2016 18:11 spinesheath wrote:
You don't need to store any permutations in memory aside from the current optimum. So you should write an enumerator that has a way to calculate the next permutation when asked for, but never stores more than maybe the last permutation.

Then you consume the output of the enumerator one at a time, check if it is better than the last, and discard it if it is not.

Performance will still be awful of course.

function fib($n)
{
    if ($n < 2) {
        return $n;
    }

    return fib($n - 1) + fib($n - 2);
}

$cache = [0, 1];

function fib_memo($n)
{
    global $cache;

    if (isset($cache[$n]) && $cache[$n] === $n) {
        return $cache[$n];
    }
	
    return $cache[$n] = fib_memo($n - 1) + fib_memo($n - 2);
}

// checked fib(38) and fib_memo(38), to keep it simple
// Results:
// fib used 15342 ms for its computations
// It spent 32 ms in system calls
// ------------------------------------------
// fib_memo used 8453 ms for its computations 
// It spent 32 ms in system calls

On December 29 2016 23:43 mantequilla wrote:
I wanna do a similar thing in java. Since you cannot pass functions as parameters, I assume you need to pass an anonymous class. Creating an anonymous class for every time you are calling a service will end up with many many classes, don't know if that will cause problems though I don't want to create big problems for a little syntactic sugar.

	public void doStuff(Consumer<SomeParameterType> successCallback, Consumer<SomeParameterType> failureCallback) {
		// ...
	}
	
	public void otherFunc() {
		doStuff(
			// success callback
			param -> { // the "param" part is just the name of the parameter. You can call it anything you like.
				// do stuff
			}, // <- notice the comma here!
			// failure callback
			param -> {
				// do other stuff
			}
		);
	}

On December 29 2016 23:43 mantequilla wrote:
Creating an anonymous class for every time you are calling a service will end up with many many classes

On December 31 2016 02:36 Targe wrote:
is anyone familiar with MPI?

im trying to determine whether the communication overhead is greater than the overhead of retrieving data from another node in a massively parallel computer

On December 31 2016 03:12 Mr. Wiggles wrote:

I've used MPI a little bit on relatively small (~8 machine) clusters as part of some course work.

Would you mind explaining your problem a little more? I'm not quite sure what you're asking from what you've written here.

On December 31 2016 03:56 Targe wrote:

im trying to decide how to approach a problem (need to write a program that repeatedly replaces the values in an array with the value of its 4 neighbours, with the exception of boundary values, until the values of the array settle to within a given precision)

i think i have access to 4 nodes (16 cores per node) and need to come up with and test a solution to the above problem

previously i wrote a program as a solution to the same problem but for an environment with shared memory rather than distributed memory

e: the idea is for the program to scale as best as possible with the number of threads so im interested in what has the most overhead

On December 29 2016 23:43 mantequilla wrote:
+ Show Spoiler +

do you guys know a better way?

class Service {
    void doWork(Callback callback) {
        doWork();
        if (work.isDone()) {
            callback.onSuccess();
        } else {
            callback.onFailure();
        }
    }
    
    interface Callback {
        void onSuccess();
        void onFailure();
    }
}

int main() {
    Service service = new Service();
    service.doWork(new Service.Callback() {
        @Override
        void onSuccess() {
            textView.setText("Done");
        }

        @Override
        void onFailure() {
            textView.setText("Failed");
        }
    })
}

On December 31 2016 05:00 Mr. Wiggles wrote:


MPI itself doesn't have that much overhead, as the major implementations are mature and optimized. Most of your overhead is going to come from communication and synchronization costs in your program. This is all very workload dependent, so I can give my thoughts, but I can only really outline what to look at.

There's obviously going to be a cost if you have to transfer data back and forth between nodes, but depending on the length of the computation and how fast you can transfer data between nodes, this might be amortized. Similarly, any time your program has to perform some kind of synchronization/communication you're going to pay an overhead based on the communication latency between your nodes.

So, your observed speedups are going to depend a lot on how much synchronization and communication needs to occur between your nodes. If you can just partition your dataset between all the nodes and let them chug away, you're likely to see good speedups. If your nodes need to constantly communicate between each other, you might hit a bottleneck.

Depending on what synchronization primitives you're using in your shared-memory program, porting to MPI may be relatively straightforward. For example, if synchronization is barrier-based, pthread_barrier_wait() transfers directly to MPI_Barrier(). MPI provides some higher-level functions which can make porting a bit nicer, but is generally pretty low-level.

If you're just interested in making one problem instance run as fast as possible, looking at distributed memory frameworks makes sense. Depending on your workload, it might also make sense to just run four different instances on each available node. In this case, it depends on if you care about throughput or response time for a single problem instance.

All in all, I can only say that MPI doesn't have much inherent overhead, and that the choice to use it basically depends on your problem and what your workload looks like. If your problem exhibits coarse granularity and doesn't require much synchronization overhead, I'd say go for it and measure what speedups you see. If there's a large amount of synchronization required, then you might not see good speedups, even if you're giving additional resources to the program.

On December 31 2016 07:46 Targe wrote:
the problem i believe requires me to synchronise all threads with every iteration (with each loop threads need the new values updated by other threads or they wont be using the right values), for the shared memory implementation i had a barrier at the end of every loop and after the threads checked whether the required precision was reached.

i need to come up with a way of passing the updated information between the threads with as little overhead as possible

On December 31 2016 07:46 Targe wrote:


sorry for being confusing, by overhead i meant to say the overhead of communication, your post is still informative though.

the problem i believe requires me to synchronise all threads with every iteration (with each loop threads need the new values updated by other threads or they wont be using the right values), for the shared memory implementation i had a barrier at the end of every loop and after the threads checked whether the required precision was reached.

i need to come up with a way of passing the updated information between the threads with as little overhead as possible

On December 31 2016 08:49 spinesheath wrote:

It sounds like you probably have some wiggle room.

I imagine this as a 2D Array, with 4 neighbours top/bottom/left/right. Naively you would probably split a 40x40 Array into 16 10x10 Arrays with an extra ring outside for synchronization, so 16 12x12 Arrays. But maybe you could also use 14x14 arrays and synchronize 2 rings every 2 iterations. Depending on the concrete environment that could improve performance.

I don't know if this is even remotely close to your actual problem, but I would suspect that there are some options whatever it is exactly. Look for less intuitive chunks to cut your problem into and compare them to what you have.

On December 31 2016 18:49 RoomOfMush wrote:

I assume the size of your problem is sufficiently big to even think about spreading it over multiple processors. In that case I would suggest calculating the values that need to be shared first, then start the communication while simultaneously working on the values that dont need to be shared. Ideally the messages from the other machines will arrive before you have finished with all the local calculations and your communication overhead becomes zero.