Multiprocessors that store the same shared data in different caches must ensure that these caches have consistent copies. Almost all known solutions to this cache consistency problem are only suitable for architectures with a few tens of processing elements (PEs). Efficient solutions to the TLB (translation lookaside buffer) consistency problem, a special case of the cache consistency problem, can be found for highly parallel, shared-memory multiprocessors (HPSMMs) with many hundreds of PEs for the following reasons: the number of references to address translation information per modification is very large; the cache for storing translation information can be present anywhere on the path from the PEs to memory; when the memory mapping needs to be modified, one can often select which translation information to change; and obsolete mapping information can be used until permanent changes must be made. Three general methods are presented that use these features and can be used on HIPSMMs to maintain TLB consistency. Some interesting issues inherent to the TLB consistency problem and the support of a demand-paged virtual memory system on a HPSMM are presented.