embedded system solution with complex System-on-Chip (SoC) to meet market expectations of high performance at a low cost and lower energy consumption. The memory architecture of the em- bedded system strongly influences crtical system design objectives like area, power and performance. Hence the embedded system designer performs a complete memory architecture exploration to custom design a memory architecture for a given set of ap- plications. Further, the designer would be interested in multiple optimal design points to address various market segments. How- ever, tight time-to-market constraints enforces short design cy- cle time. In this paper we address the multi-level multi-objective memory architecture exploration problem through a combination of exhaustive-search based memory exploration at the outer level and a two step based integrated data layout for SPRAM-Cache based architectures at the inner level. We present a two step inte- grated approach for data layout for SPRAM-Cache based hybrid architectures with the first step as data-partitioning that parti- tions data between SPRAM and Cache, and the second step is the cache conscious data layout. We formulate the cache-conscious data layout as a graph partitioning problem and show that our ap- proach gives up to 34% improvement over an existing approach and also optimizes the off-chip memory address space. We exper- imented our approach with 3 embedded multimedia applications and our approach explores several hundred memory configura- tions for each application, yielding several optimal design points in a few hours of computation on a standard desktop.