To perform a data replace control activated prior to the execution of a cache memory reference instruction so as to reduce the latency when a miss occurs to a cache memory. In a cache replace control of a load store unit, a load store unit controlling device comprises a first queue selection logical circuit 41, a second queue selection logical circuit 42 and a mediating unit 43, wherein the first queue selection logical circuit sequentially selects access instructions to access the cache memory which are stored in queues 31, wherein the second queue selection logical circuit selects unissued access instructions of the access instructions to access the cache memory which are stored in the queues prior to the selections by the first queue selection logical circuit, and wherein the mediating unit mediates between the access instructions selected by the first queue selection logical circuit and the pre-access instructions selected by the second queue selection logical circuit for accessing the cache memory.