39

So a paper exists, it was published 3 years ago and had a novel algorithm (more or less, it's in the area of finite-difference time-domain simulations).

I've taken the algorithm and accelerated it by a factor of 100x (example, I don't have the true number), producing the same results in the end, but providing an opportunity to essentially simulate more (iterations/objects) in the same amount of time.

The methods used to accelerate it aren't particularly novel, though some aspects might very well be a bit different from mainstream ideas. All in all, a person set out to do the same thing would probably be able to do it, but I would not call it trivial. However, I know that this has not been done before.

Is this something worth publishing? I am going to ask my supervisor, but he's been very busy lately ( >.< ), I haven't been able to catch him for ~4 days. I would like some of your opinions.

  • 14
    Did you make an algorithmic improvement that improved the asymptotic complexity (from e.g. O(n^2) to O(n*log(n)), or simply write a highly tuned implementation of the same algorithm? – Brian Borchers Nov 6 '14 at 0:32
  • @BrianBorchers, it depends if you consider parallel implementations a change in complexity (I think of it that way, but I don't know if that's an accepted view). I think the time complexity has changed because it scales differently with n now. – Mewa Nov 6 '14 at 1:14
  • Also I should mention, the algorithm is implemented in simulation software, so I think there are people who would like having my version, but I don't know if it should be published. – Mewa Nov 6 '14 at 1:28
  • 21
    @Mewa Such papers are publishable, and that's from personal experience. My very first paper used high-school math (Gaussian Elimination) within a context (homography estimation in computer vision) where the use of the expensive SVD decomposition was all but standard and we got a massive 70x speedup over the state of the art in OpenCV (the popular computer vision library) while not damaging accuracy too much, making it possible to run real-time on mobile phones and embedded platforms. The paper was published in CVPR Workshops 2014 this past summer! – Iwillnotexist Idonotexist Nov 6 '14 at 6:54
  • 2
    From personal experience, such results are absolutely publishable. – drxzcl Nov 6 '14 at 10:55
47

If I understand the question correctly, the dilemma is whether to just distribute the code or whether to also make a scientific publication out of it. The way that I typically think about this type of problem is to see whether it passes any of the following tests:

  1. Does the improvement enable a significant scientific or technical work that was not previously possible? For example, if faster simulation allows a control loop to be done in realtime that couldn't before, that advance may be scientifically valuable even if the methods are not interesting in and of themselves, but you have to demonstrate that value.

  2. Does the improvement make a qualitative change in the operation of the algorithm which is interesting, e.g., changing a scaling property that was previously a limit?

  3. Is the mechanism of the improvement interesting in and of itself, e.g., such that it teaching something about the nature of the algorithm or such that it might be applied to other algorithms or problems as well?

Any of these is a good reason to publish an improvement on an algorithm.

  • Thanks Jake! That makes sense. I think it fits (1) and (2) fairly well. Not sure about (3) so much, but I'll definitely take a closer look. Maybe it can be useful for other FDTD simulations. – Mewa Nov 6 '14 at 4:43
16

@jakebeal answer is spot-on, but I will add my extra two cents. As you said you parallelized the algorithm, which is good but how did this happen?

  • Was the algorithm already parallel and just has not been implemented that way? If yes, simply parallelizing the implementation might not be good enough.

  • Did you used other additional optimizations to make it efficient? For example did you use SIMD (SSE, AVX) instructions or GPUs for your implementation?

  • As jakebeal said, did you alter the scope of the algorithm? If the algorithm could handle e.g. only small graphs up to a size, with your implementation it might scale to much larger graphs.

  • If, for example you worked on an indexing method, did your method improved the building of the index or also improved the index's query performance?

The most important thing to consider, is that you need to write a full paper to present your improved version. So, if all you can say is "I parallelized the algorithm with OpenMP and is now faster" or "I vectorized this loop" and other technical details, this will not be good enough for a scientific paper. On the other hand, if you worked on advanced techniques (SIMD, GPUs), your work might worth a publication. Still, it might not be good enough for top-algorithm conferences (where new algorithms are usually presented) and might be more suitable for conferences focused in parallel algorithms, implementations, which are more focused on the technical side of things. Also, I would worry about the fact that no one touched this algorithm for 3 years. Are you sure there is not another algorithm that is now the state-of-the-art for this particular problem? You should look into this too.

Update: Since you already have a done a GPU-CUDA version of this algorithm, it would be interesting to actually extend your work on plain multicores with a) OpenMP (that would be trivial) b) OpenMP + SIMD (that would be harder c) or OpenMP + SIMD + partial CUDA. Having several tuned versions of the same algorithm for different architectures and performance benchmarks for the different versions, would make a much stronger paper.

  • Thanks, Alexandros. I don't want to go into too much detail, but basically: (1) No, it wasn't. It's a very sequential implementation. (2) I used a GPU (CUDA). (3) Technically it can simulate greater number of nodes now. Also I think 3D would be more feasible (it's 2D right now though). I haven't tried 3D yet. SIMD is an interesting idea (I've done it before on microprocessors), maybe I'll try that too. I'm not sure why it hasn't been moved to GPUs yet, but I talked to the authors in June (in person) and they were still working on it then. It's not that big of a deal if it isn't published. – Mewa Nov 6 '14 at 4:45
  • Continued: It is part of my MSc thesis, so if it just takes up a chapter, that's ok too :) I thought publishing might be nice though. And yeah, I was going to go for some parallel processing group rather than algorithms. Maybe something like IEEE PADS. – Mewa Nov 6 '14 at 4:49
  • 1
    You could also try Euro-Par. – Alexandros Nov 6 '14 at 4:52
  • @Mewa See my edit – Alexandros Nov 6 '14 at 7:18
  • Regarding different platforms, it depends on the target audience. Most computing clusters I have access to have CUDA enabled cards, so that would be enough. If you want users to run it on their computers, OpenCL is better, because it can run on CPU too. – Davidmh Nov 6 '14 at 10:20
6

One option that you have is to submit a paper to a demo session of a conference. Such papers usually describe existing systems so they don't have to be new. If you are accepted, your paper is published in the proceedings, and you have the right to present a live demo of your system in the conference. If your improved implementation indeed makes 3D possible, you may have a very impressive demo.

5

How is your code faster than the state of the art? If it's faster only because you're a good programmer, you're unlikely to be able to publish in a worthwhile venue. If it's faster because you did some computer science, you might be onto something.

  • 3
    Nice, I'm a professional programmer and I just read all the other answers thinking, "what? I optimise code from time to time, never occurred to me I could get a paper out of it!" :-) – Steve Jessop Nov 6 '14 at 14:18
  • 2
    @SteveJessop If the scale of improvement is outrageously large enough and the software is relevant to the scientific community, a paper combined with an opensource implementation can be worth trying. In such a paper, be prepared to explain the design decisions and demonstrate you have not lost something for all that speed. It's fun when your implementation becomes the gold standard. – Iwillnotexist Idonotexist Nov 6 '14 at 15:10
  • 1
    That's fair. I am going to talk to some CS people (we share the floor, so I don't even have to walk anywhere!) and see what they think. I was thinking this would be more appropriate to publish in the area for which the algorithm is used rather than CS/algorithms/even parallel programming to some extent. – Mewa Nov 6 '14 at 16:47
  • Also, obviously I attribute the fact that I get anything working to the aspect of me not being absolutely awful, but I would have thought migrating to a different hardware (GPU in this case) would go a bit beyond the normal optimization (unrolling loops, inlining, etc). – Mewa Nov 6 '14 at 21:36
  • 2
    @Mewa Maybe, maybe not. Porting code from PC to Mac wouldn't be a paper, for example. – David Richerby Nov 6 '14 at 21:44
1

I have also published some papers in the same vein. If you can find something novel about your implementation (significant changes to the algorithm, novel optimizations, new insights about the architecture, etc.) then you have a better chance of getting published. If you only achieved the speedup by parallelizing the algorithm in a straightforward fashion, it will stand less of a chance at the higher tier conferences. 5 or 6 years ago when GPGPU programming was still very new, people were often publishing papers about GPU parallelized algorithms. This is becoming less frequent now, because many of the fundamental concepts about this process have already been explored. Much of the low hanging fruit in that area has been picked, so reviewers will tend to view straightforward parallelization of algorithm "X" as not very novel.

0

I'd say simply write a paper, submit it at one of the top venues in that area and let the reviewers decide for you. If it was rejected they will suggest the changes that could get it accepted in the following conference.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.