CAD/BIM Taskforce: Addressing Challenges in Digital Design Preservation

Slide Note

The CAD/BIM Taskforce focuses on preserving digital design files by addressing challenges in technology, access, and description. From developing standards to discussing workflows, the taskforce aims to create a universal reference point for institutions dealing with digital content preservation. Explore their approach, current questions, and deeper dives into topics like deed of gift analysis and acquisition tools.

waer573 Follow

Uploaded on Mar 16, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

Umbra: Efficient and Scalable Memory Shadowing Qin Zhao (MIT) Derek Bruening (VMware) Saman Amarasinghe (MIT) CGO 2010, Toronto, Canada April 26, 2010

Shadow Memory Meta-data Track properties of application memory Synchronized Update Application data and meta-data a.out a.out heap heap libc libc stack stack Application Memory Shadow Memory 2 CGO, Toronto, Canada, 4/26/2010

Examples Memory Error Detection MemCheck [VEE 07] Purify [USENIX 92] Dr. Memory MemTracker [HPCA 07] Dynamic Information Flow Tracking LIFT [MICRO 39] TaintTrace [ISCC 06] Multi-threaded Debugging Eraser [TCS 97] Helgrind Others Redux [TCS 03] Software Watchpoint [CC 08] 3 CGO, Toronto, Canada, 4/26/2010

Issues Performance Runtime overhead Example: MemCheck 25x [VEE 07] Scalability 64-bit architecture Dependence OS Hardware Development Implemented with specific analysis Lack of a general framework 4 CGO, Toronto, Canada, 4/26/2010

Memory Shadowing System Dynamic Instrumentation Context switch (application Address calculation Updating meta-data shadow) Memory Management Memory allocation / free Monitor application memory management Manage shadow memory Mapping translation scheme (addrA addrS) DMS: Direct Mapping Scheme SMS: Segmented Mapping Scheme 5 CGO, Toronto, Canada, 4/26/2010

Direct Mapping Scheme (DMS) Single memory region for entire address space. Translation: Issue: address conflict between memA and memS = + addr addr disp S A lea [addr] add %r1 disp %r1 %r1 Application 5 4.67 Slowdown relative to 4 native execution 3 2.40 1.80 2 Shadow 1 0 DMS-32 SMS-32 DMS-64 SMS-64 6 CGO, Toronto, Canada, 4/26/2010

Segmented Mapping Scheme (SMS) Shadow segment per application segment Translation: Segment lookup (address indexing) Address translation = + addr addr disp S A seg lea [addr] mov %r1 shr %r2, 16 add %r1, disp[%r2] %r1 %r2 %r2 %r1 addrA App 1 5 4.67 Shd 2 Slowdown relative to addrS 4 Shd 1 native execution 3 2.40 Segment table 1.80 2 App 2 1 0 DMS-32 SMS-32 CGO, Toronto, Canada, 4/26/2010 DMS-64 SMS-64 7

Umbra Mapping Scheme Segmented mapping Scale with actual memory usage Implementation DynamoRIO Optimization Translation optimization Instrumentation optimization Client API Experimental Results Performance evaluation Statistics collection 8 CGO, Toronto, Canada, 4/26/2010

Shadow Memory Mapping Scaling to 64-bit Architecture DMS Infeasible due to memory layout a.out User space stack 247 Unusable space Kernel space vsyscall 264 9 CGO, Toronto, Canada, 4/26/2010 CGO, Toronto, Canada, 4/26/2010

Shadow Memory Mapping addrA Scaling to 64-bit Architecture DMS Infeasible due to memory layout Single-Level SMS Too big (~4 billion entries) 10 CGO, Toronto, Canada, 4/26/2010

Shadow Memory Mapping addrA Scaling to 64-bit Architecture DMS Infeasible due to memory layout Single-Level SMS Too big (~4 billion entries) Multi-Level SMS Even more expensive Fast path on lower 32G (MemCheck) Slowdown relative to 5 4.67 4 native execution 3 2.40 1.80 2 1 0 DMS-32 SMS-32 DMS-64 SMS-64 11 CGO, Toronto, Canada, 4/26/2010

Shadow Memory Mapping Scaling to 64-bit Architecture DMS is infeasible Single-Level SMS is too sparse Multi-Level SMS is too expensive Umbra Solution Eliminate empty entries Compact table Walk the table to find the entry 12 CGO, Toronto, Canada, 4/26/2010

Umbra Mapping Scheme Segmented mapping Scale with actual memory usage Implementation DynamoRIO Optimization Translation optimization Instrumentation optimization Client API Experimental Result Performance evaluation Statistics collection 13 CGO, Toronto, Canada, 4/26/2010

Implementation Memory Manager Monitor and control application memory allocation brk, mmap, munmap, mremap Allocate shadow memory Maintain translation table Instrumenter Instrument every memory reference Context save Address calculation Address translation Shadow memory update Context restore App 1 Shd 2 Shd 1 App 2 14 CGO, Toronto, Canada, 4/26/2010

Umbra Mapping Scheme Segmented mapping Scale with actual memory usage Implementation DynamoRIO Optimization Translation optimization Instrumentation optimization Client API Experimental Result Performance evaluation Statistics collection 15 CGO, Toronto, Canada, 4/26/2010

Unoptimized System ~100 20 Small overhead from DynamoRIO Slower than SMS-64 Need to walk the global translation table 18 15.815.2 16 14 12.0 12 10 8.3 8 4.7 6 3.1 2.5 4 Why so slow? 41.79% instructions are memory references For each of these instructions Full context switch Table lookup Call-out instrumentation 1.1 2 0 Memoization Reference SMS-64 Context Switch DynamoRIO Local Translation Hash Table Reference Cache Unoptimized Grouping Reduction Check Table Global translation table 16

Optimization ~100 20 Translation Optimization Thread-local translation cache Hashtable lookup Memoization mini-cache Reference uni-cache 18 15.815.2 16 14 12.0 12 10 8.3 8 4.7 6 3.1 2.5 4 1.1 2 0 Memoization Reference SMS-64 Context Switch DynamoRIO Local Translation Hash Table Reference Cache Unoptimized Grouping Reduction Check Table Instrumentation Optimization Context switch reduction Reference grouping 3-stage code layout Global translation table 17 17

1. Thread-Local Translation Cache ~100 20 Local translation table per thread Synchronize with global translation table when necessary Avoid lock contention Walk table to find match entry Walk global table if not find in thread-local cache Inlined instrumentation 18 15.815.2 16 14 12.0 12 10 8.3 8 4.7 6 3.1 2.5 4 1.1 2 0 Memoization Reference SMS-64 Context Switch DynamoRIO Local Translation Hash Table Reference Cache Unoptimized Grouping Reduction Check Table Thread 1 Thread 2 Global translation table Thread-local translation cache 18

2. Hashtable Lookup ~100 20 Hashtable per thread Fixed number of slots Hash(addra) entry in thread-local cache If match, found If no match, walk the local cache 18 15.815.2 16 14 12.0 12 10 8.3 8 4.7 6 3.1 2.5 4 1.1 2 0 Memoization Reference SMS-64 Context Switch DynamoRIO Local Translation Hash Table Reference Cache Unoptimized Grouping Reduction Check Table Thread 1 Thread 2 Global translation table Thread-local translation cache Hashtable 19

3. Memoization Mini-Cache ~100 20 Four-entry table per thread Stack Heap Application (a.out) Units found in last table lookup If not match, hashtable lookup 68.93% hit ratio 18 15.815.2 16 14 12.0 12 10 8.3 8 4.7 6 3.1 2.5 4 1.1 2 0 Hashtable Reference SMS-64 Context Switch DynamoRIO Local Translation Unoptimized Reference Uni- Memoization Mini- Grouping Reduction Cache Table Cache Thread 1 Thread 2 Global translation table Memoization mini-cache Thread-local translation cache Hashtable 20

4. Reference Uni-Cache ~100 20 Software uni-cache per instr per thread Last reference unit tag Last translation displacement If not match, memoization mini-cache check 99.93% hit ratio 18 15.815.2 16 14 12.0 12 10 8.3 8 4.7 6 3.1 2.5 4 1.1 2 0 Hashtable Reference SMS-64 Context Switch DynamoRIO Local Translation Unoptimized Reference Uni- Memoization Mini- Grouping Reduction Cache Table Cache ADD $1, (%RAX) Thread 1 MOV %RBX 48(%RAX) PUSH %RAX Thread 2 ADD 40(%RAX), %RBX Reference uni-cache Global translation table Memoization mini-cache Thread-local translation cache Hashtable 21

5. Context Switch Reduction ~100 20 Register liveness analysis Use dead register Avoid flags save/restore 18 15.815.2 16 14 12.0 12 10 8.3 8 4.7 6 3.1 2.5 4 #/#Instr SPEC2006 1.1 2 Memory Reference 41.79% 0 Hashtable Reference SMS-64 Context Switch DynamoRIO Local Translation Unoptimized Reference Uni- Memoization Mini- Grouping Eflag Steal 2.55% Reduction Cache Register Steal 8.20% Table Cache ADD $1, (%RAX) Thread 1 MOV %RBX 48(%RAX) PUSH %RAX Thread 2 ADD 40(%RAX), %RBX Reference uni-cache Global translation table Memoization mini-cache Thread-local translation cache Hashtable 22

6. Reference Grouping ~100 20 One reference cache for multiple references Stack local variables Different members of the same object 18 15.815.2 16 14 12.0 12 10 8.3 8 4.7 6 3.1 2.5 4 1.1 2 0 Hashtable Reference SMS-64 Context Switch DynamoRIO Local Translation Unoptimized Reference Uni- Memoization Mini- Grouping #/#Instr SPEC2006 Reduction Cache Table Cache Memory Reference 41.79% Ref Uni-Cache Checks 22.76% ADD $1, (%RAX) Thread 1 MOV %RBX 48(%RAX) PUSH %RAX Thread 2 ADD 40(%RAX), %RBX Reference uni-cache Global translation table Memoization mini-cache Thread-local translation cache Hashtable 23

3-stage Code Layout Inline stub (<10 instructions) Quick inline check code with minimal context switch Lean procedure (~50 instructions) Simple assembly procedure with partial context switch Callout (C function) C function with complete context switch Lean procedure Callout Inline stub uni-cache check <full context switch> c_function() { // global table // lookup . . . . . . } <full context switch> memoization check app instruction hashtable lookup local cache lookup 24 CGO, Toronto, Canada, 4/26/2010

Umbra Mapping Scheme Segmented mapping Scale with actual memory usage Implementation DynamoRIO Optimization Translation optimization Instrumentation optimization Client API Experimental Result Performance evaluation Statistics collection 25 CGO, Toronto, Canada, 4/26/2010

Client API Event Hooks client_init client_exit client_thread_init client_thread_exit shadow_memory_create shadow_memory_delete instrument_update Description Process initialization Process exit Thread initialization Thread exit Shadow memory creation Shadow memory deletion Insert meta-data update code 26 CGO, Toronto, Canada, 4/26/2010

Umbra Client: Shared Memory Detection Meta-data maintains a bit map to store which threads access the associated memory static void instrument_update(void *drcontext, umbra_info_t *umbra_info, mem_ref_t *ref, instrlist_t *ilist, instr_t *where) { /* lock or [%r1], tid_map [%r1] */ opnd1 = OPND_CREATE_MEM32(umbra_info reg, 0, OPSZ_4); opnd2 = OPND_CREATE_INT32(client_tls_data tid_map); instr = INSTR_CREATE_or(drcontext, opnd1, opnd2); LOCK(instr); instrlist_meta_preinsert(ilist, label, instr); } 27 CGO, Toronto, Canada, 4/26/2010

Umbra Mapping Scheme Segmented mapping Scale with actual memory usage Implementation DynamoRIO Optimization Translation optimization Instrumentation optimization Client API Experimental Result Performance evaluation Statistics collection 28 CGO, Toronto, Canada, 4/26/2010

Performance Evaluation 4.67 5.0 Slowdown relative to 4.5 4.0 native execution 3.5 3.0 2.49 2.40 2.5 1.80 2.0 1.5 1.0 0.5 0.0 DMS-32 SMS-32 SMS-64 Umbra-64 29 CGO, Toronto, Canada, 4/26/2010

EMS64: Efficient Memory Shadowing for 64-bit Translation Reference uni-cache hit rate: 99.93% Still need a costly check to catch the 0.07% Reg steal; save flags; compare & jump; restore = + disp . addr addr rc S A EMS64 (ISMM 10) Speculatively use a disp without check Notified by memory access violation fault for incorrect disp 30 CGO, Toronto, Canada, 4/26/2010

EMS64 Preliminary Result 5.0 4.67 4.5 Slowdown relative to 4.0 3.5 native execution 3.0 2.49 2.40 2.5 1.81 1.80 2.0 1.5 1.0 0.5 0.0 DMS-32 SMS-32 SMS-64 Umbra-64 EMS-64 31 CGO, Toronto, Canada, 4/26/2010