If the assimilation is such a computation-intensive task, why don't they assign each pop a random number between 1 and 10, and only update 1/10 every day? Thus cycling through the entire world POPulation in 10 (or 14?) days. I don't see why they all have to be updated daily. At least not their assimilation logic. Perhaps even their revolt / needs / everything else logic could do with only being updated once in 10 or 14 days??
If that is possible you'd then be able to do something with the assimilation logic. My favorite approach would be to assign each culture to one of five broad "meta-ethnic groups", such as "european", "eastasian", "african", "indian", "muslim", and then let the little POPs assimilate towards the biggest ethnicity within that group. afro-carribean POPs in a US province would assimilate towards whatever is the biggest culture in the "african" subset in their province, while a Gujarati pop would assimilate towards the biggest ethnicity in the "indian" or "southasian" group. National or accepted cultures would be weighted with a factor of x3 when comparing who's the biggest culture in a province.
If that creates too little assimilation towards the primary culture, then you could have a second, simple mechanism parallel to this one whereby within a "meta-ethnic group" each pop asimilates a little towards the national culture.
It's not really more complicated than King's original idea. There is some more computation but you have to count each POP anyways in each province... No POP could be in more than one "meta-ethnic group" so I think you'd end up with just as much computation.
(And yes, you could call them "races" instead of "meta-ethnic groups" but we're not 19th century chauvinists...)
The nice thing about this is that you don't remove those interesting small emigrant communities. American provinces will retain afro-american communities, because all immigrant pops from the "african" group assimilate into afro-american. Indian communities within the British Empire don't assimilate into British but into whatever is the largest local indian culture. Maybe it's Gujarati in Cape Town, and Kannada in Sidney? Mahatma Gandhi was a Gujarati immigrant in British South Africa and despite being having studied Law in London he never assimilated to consider himself British. However he blended in with the local Indians and became part of their community. Having POPs pick assimilation targets from within a larger racial or meta-ethnic group would let you have exactly that in your game, *AND* it would still rid you of the small POPs.
You could probably even increase the assimilation speeds, because contrary to what King proposed or to what's implemented right now, you retain the broader ethnic makeup of your empire.