I would say parallel concerns, for the big architectural-level concepts, are something you should anticipate very upfront, and it relates to thinking about data as Michael Borgwardt pointed out.
A Serial Design Mindset
I had difficulty achieving the level of parallelism I've achieved in recent years because, for many years, I was still thinking in a very serial type of way about the overall architecture, and that was the case in general for my industry (VFX). Most of our competitors apply a very serial mindset to the bulk of the architecture, and typically lock and copy hefty data structures around for the few cases where parts of their pipeline can run in parallel (like an interactive offline renderer which spends a good time starting up copying the entire application state). I still managed to get some good CPU utilization in the heavy-lifting areas by parallelizing loops with Intel's Thread Building Blocks and OpenMP and so forth as well as using the GPU and SIMD and what not, but it was still a largely serial sort of pipelined architecture in previous versions.
So I used to insist not too long ago, for example, that any physics simulation designed for real-time purposes should run at hundreds to thousands of frames per second on real-world input cases, not a mere 60 FPS in some demo. I was a bit of a hard ass this way insisting that such frame rates were not good enough, because I was still thinking in a serial fashion and coming from a former gamedev standpoint. I thought since physics "mutates scenes", it must run very quickly or else it would cut into all the other things going on besides physics which would have to wait for such mutations to occur (or at least deal with lots of locking) and we'd lose the real-time interactivity (which did often happen and sometimes we had slide shows where users expected real-time feedback; I might have been a bit of a hard ass about this stuff but we did suffer real issues and many user complaints because of this).
A New Kind of Performance
Fast forward and now we're running physics in parallel with real-time rendering in parallel with things users are doing like modeling and animating also running in parallel. It's all running in parallel and the pipeline is a parallel one instead of the sort of serial ones we had in the past only using threads to make each section finish faster so that other parts don't have to wait as long. And it's flying; the slide show frame rates and the application becoming unresponsive are a thing of the past.
But there's no way we could have achieved that in hindsight using the sort of designs of data we had in the past. I had to move away from the whole idea that, say, physics mutates the application's central scene. Instead now it inputs scenes and outputs new scenes with physics applied to the new scene it outputs (physics is now "pure" in the sense that it has no externals side effects), and to do that efficiently I had to study how functional programmers achieve this with persistent data structures (the scenes otherwise often take gigabytes of data which would be very expensive to deep copy in full all over the place). And that took a lot of upfront effort and research and some rethinking about things I took for granted many years.
Yet once we got that basic idea working, we were flying and never looking back. Because it not only yielded more interactive frame rates than we ever saw before with less effort to do so, but it also simplified everything, made the systems easier to think about, and actually made it so I no longer thought of physics as having to run hundreds to thousands of frames per second. When all these other parts of the pipeline, like the real-time renderer, don't have to wait on physics before they can do their thing, then it can suffice for the physics to merely run at 60 frames per second because it can be cranking out a new output with physics applied while the renderer is simultaneously rendering its previous output as well as having more things to render in the meantime with the other things going on in the pipeline that are outputting new scenes.
It actually reduced emphasis on efficiency to some degree, because it was no longer as critical for user-end performance for everything involved in delivering a frame for the user to see to finish as quickly as possible when other things aren't waiting for that to finish. And I can't overstate how much of a load off that has been in cases where the real-time interactivity of the software should not be compromised too much.
The Mindset
[...] make sure its implemented correctly, and then parallelize it OR should one proceed to writing the parallelization from the beginning?
To me it's not so critical to parallelize the code in the beginning so much as consider how you design the data upfront so as to make it possible to parallelize to your hearts' content. Doors open up to parallelize things you might have never thought to do so if you design the data appropriately, and at the broad architectural level where you get the most bang for the buck, not some simple loop used to implement one thing that you can reason about as being thread-safe.
This might be somewhat biased but if your desires to parallelize code constantly have you questioning thread safety and trying to figure out where you need thread synchronization, then the data might not be designed appropriately for such concurrency. I have found the greatest yields, and simplicity on top of performance, coming by seeking out designs that make thread-safety a no-brainer without even concerning ourselves with synchronization, which basically boils down to making big sections of the architecture input data and output new data as opposed to inputting data and mutating it.
A lot of that came about by seeking to make things "pure" (free of external side effects). And in my case such "purity" can involve things at a coarser design level than a single function or immutable object or what not. The entire physics system that I was talking about above, although composed of multiple objects and functions, is now "pure" (even though it mutates some state local to its own thread) in the sense that it causes no external side effects to the central application state (the "Scene"). So it's free to run in parallel just inputting a scene and outputting a new one with physics applied.
Concurrency Overhead
One other point perhaps worth mentioning is that it might be required, to design data for this type of concurrency I describe, for it come with quite a bit of overhead. Generally you shouldn't expect a non-trivial data structure designed for concurrency to outperform one that's not when benchmarking in a single thread.
And we certainly have that sort of "single-threaded overhead" in our new scene design, which actually takes almost 3 times longer to generate a modified version (it doesn't mutate/touch the original scene, it creates a new one) and ~25% longer to access for read-only purposes (we have an additional level of indirection to allow cheap shallow copying of unmodified parts) when benchmarking its efficiency in a single thread, than our former scene design, in exchange for dirt cheap copying and the ability to modify just parts of the scene without deep copying the untouched parts to allow our pipeline to just copy it all over the place with minimal processing/memory cost and output new, modified versions.
But the exchange has been more than worth it when we're able to run all these parts of our central architectural pipeline in parallel. The end result, from the user-end perspective with all these things running in parallel, is more performant and interactive and real-time than anything we've ever designed before. But I'd say that's a common concern you might face with a serial mindset is that the parallel design to the data might incur some more redundancy, or some form of overhead, in order to make it work more effectively in parallel, and in my cases that quickly became a non-concern as we saw more interactive and real-time frame rates than we ever saw before.
Cheap Copying
So one of the things worth pointing out is that in any sane architecture (like not one using globals all over the place), we can take any hefty operation and make it thread-safe by simply making it no longer mutate its inputs. Instead we can make it copy its input, start modifying the copy, and output the modified copy when it's finished. Now we can invoke the "operation" (which is now more like an "evaluator" since it's just inputting something and outputting something), in parallel without worrying about how its side effects interact with other things because there are no external side effects anymore.
An alternative is to make all such data structures we pass in safe for concurrent read and write access, like lock-free concurrent data structures (the concurrent queue being a popular example). I explored that route for a while but it became too difficult in our case to make every single thing from the scene data structure to everything in it safe for concurrent reads and writes, not to mention that it raised a lot of user-end design questions. For example, if the user is performing a modeling operation in parallel like a CSG operation on a mesh/model, then rendering it simultaneously would be safe in a basic sense of avoiding race conditions if that shared mesh data is safe for concurrent reads and writes, but it would create rendering artifacts if the user saw a frame being displayed in the middle of the operation before it is finished. That's just one example but it felt like we were opening up a can of worms if we sought to make all the relevant, underlying data structures safe for concurrent reads and writes.
So we came back to the copying idea except there was a bit of a problem there. Our scene data often spans gigabytes in real-world production cases; in fact most of our example content that we acquired from professional artists working on films and so forth spanned gigabytes of memory with very high-res models and textures and things of this sort. You might imagine how explosive the memory use of the software would be and how bottlenecked it'd be in copying this memory over and over for every thread in every frame if that data had to be deep copied in full every time.
The solution was to make the data cheap to copy. The parts that aren't touched are shallow copied and use a garbage collection sort of approach with shared ownership between the previous copies for the parts that are untouched. Only the parts that are touched are deep copied and made unique in a given modified copy of a scene. Then we were able to copy the scene left and right without explosive copying overhead and memory use.
That ability to copy around these hefty data structures without worry also simplified so many things besides concurrency because, for example, now our undo system just copies the entire scene. Undoing/redoing just swaps entire old copies of the scene with the current one. Non-destructive editing became really simple for the same reason. Exception-safety is a no-brainer in most of the code because if an operation encounters an exception halfway in the process of producing a modified output, there are no external side effects to roll back (the copy is simply discarded).
So that's one alternative and sometimes much simpler strategy is to, instead of making all your hefty data structures safe for concurrent read/write access, make them dirt cheap to copy around and produce modified copies. Then you can make hefty parts of your pipeline "pure" and free of external side effects and safe to evaluate across different threads.
