In this work, a novel design and optimization method for programmable gate macro blocks (PGMB) in the newly proposed Asynchronous Nanowire Reconfigurable Crossbar Architecture (ANRCA) is presented. ANRCA is based on a self-timed logic referred to as the Null Convention Logic (NCL). Since there is no global clocking and clock distribution network, all failure modes related to timing will be either eliminated or relaxed. The proposed architecture is anticipated to have higher manufacturability and robustness that are critical factors in nanoscale systems due to nondeterministic nature of nanoassembly. In order to facilitate efficient programming and flexible reconfiguration, a new hierarchical reconfigurable architecture for ANRCA is also proposed. Various configurable logic block structures have been considered and also their programming and reconfiguration issues are discussed.