Since you are CPU-limited, you need to get your hands on 150 CPU cores, one for each thread. This rules out a single server, since a server of such proportions would be prohibitively expensive – and you don't really need it.
Your general architecture with a common frontend that distributes work to multiple workers and combines their results appears to be sensible. You'll have to do some calculations to find the most cost-effective solution to get that many CPUs. That tends to point towards AWS Lambda since you only require computations in bursts, but it may come with restrictions. How many Lambdas may execute simultaneously? 150 at once is a lot. Which languages can you use; can you reduce your cost by using optimized native code? Importantly, I don't think Amazon makes specific performance guarantees for that product, whereas you have more control over the physical CPU with more traditional instance types.
And the actual CPU performance is important for you. While you are willing to kill the computation after 5 seconds, the amount of computation performed until then may vary wildly. You could probably manage to get 150 cores rather cheaply by running a Beowulf-cluster of Raspberry Pi boards in your basement, but that is not remotely comparable to the computation power of five high-end Intel Xeon servers.
It is therefore important that you clearly define your performance goals and a SLA and then test a proposed solution. You will also have to think about simultaneous requests. Given the high amount of computations per client request, it may be best to process client requests sequentially if that is acceptable for the clients. But this also puts an upper limit on the clients you can support, since the probability that a client has to wait before their request can be processed grows rather quickly (related to the birthday paradox).
This is a scalability problem. You can either delay it by scheduling client requests as to avoid simultaneous requests, or gain the ability to handle multiple requests in parallel. That in turn can either be managed by throwing more money/servers at the problem, or by performance-tuning of the algorithm. E.g. I've seen a case where a Python program could be made 3× faster by profile-guided optimizations like extracting an instance attribute access out of a very tight loop. The biggest wins always come from algorithmic complexity reduction, if they are possible.